Родился 15 мая 1912 года в деревне Кочерово (ныне Житомирский район Житомирской области Украины). В рядах Красной Армии с 10 сентября 1931 по 1934 гг. и с 1938 года, призван Радомышльским РВК (Житомирской области). Окончил военную авиационную школу лётчиков.

С 22 июня 1941 года сержант А. А. Павленко в действующей армии. По июль 1942 года воевал в составе 15-го ИАП (8-я САД / ИАД), летал на МиГ-3. Затем проходил переучивание на новую технику в 14-м ЗИАП и 2-м УТАП. С сентября 1942 по март 1943 гг. воевал в 21-м ИАП (209-я ИАД), где летал на ЛаГГ-3. С 8 мая 1943 года младший лейтенант А. А. Павленко - лётчик 163-го ИАП (273-я ИАД, 336-я ИАД), летая на Як-7 и Як-9. За годы войны прошёл путь от рядового пилота до командира эскадрильи. Сражался на Северо-Западном, Калининском, Центральном, Белорусском, 2-м Белорусском, 1-м Белорусском, 3-м Прибалтийском, 1-м Прибалтийском, 2-м Прибалтийском и Ленинградском фронтах. 30 мая 1944 года был сбит в воздушном бою, спасся на паорашюте. Дважды был ранен: легко - в 1943 и тяжело - в 1944 гг.

К 9 мая 1945 года командир эскадрильи  163-го истребительного авиационного полка  (336-я истребительная авиационная дивизия, 15-я Воздушная армия, Ленинградский фронт) старший лейтенант А. А. Павленко совершил 119 боевых вылетов, в 28 воздушных боях сбил лично 10 самолётов противника.

После окончания войны продолжал служить на различных должностях в ВВС. С 18 апреля 1958 года подполковник А. А. Павленко - в запасе.

Награждён орденами: Красного Знамени (27.07.1943, 01.05.1944, 27.12.1944, 30.12.1956), Отечественной войны 1-й степени (12.05.1945, 11.03.1985), Красной Звезды (30.04.1954); медалями, в том числе "За боевые заслуги" (30.04.1947).