В 1939 году окончил Курсы высшей подготовки штурманов при Военно-воздушной инженерной академии. Участник советско-финской войны 1939–1940 годов. Совершил 15 вылетов на бомбардировку военных объектов противника. В 1940 году был награжден орденом Красного Знамени за успешные боевые вылеты на фронте и медалью «За трудовое отличие» за успехи в навигации 1939 года.
Весть о нападении фашистской Германии на СССР встретил в воздухе в полете на ледовую разведку в Карском море в экипаже М. В. Водопьянова. Всем экипажем на своем самолете вылетели в Москву и были направлены в формируемый полк дальних бомбардировщиков. На фронтах Великой Отечественной войны с июля 1941 года — штурман эскадрильи 746-го авиационного полка 81-й авиационной дивизии авиации дальнего действия, майор. В августе 1941 года в экипаже командира авиадивизии М. В. Водопьянова Штепенко был флагштурманом одного из налётов советских бомбардировщиков на Берлин и, стартовав с фронтового аэродрома, точно вывел группу на немецкую столицу, первым нанеся удар по её военным объектам.
В одном из боевых вылетов осенью 1941 года Штепенко совершил уникальный по точности сброс бомб: при сильном боковом ветре положил 10 бомб точно по длине движущегося эшелона с боеприпасами. За 12 успешных боевых вылетов 20 февраля 1942 года был награжден вторым орденом Красного Знамени и 22 апреля 1942 года за следующие 16 результативных ночных боевых вылетов в экипаже майора С. А. Асямова был представлен к званию Героя Советского Союза.
Штурман эскадрильи 746-го авиационного полка (АДД), майор Штепенко к концу апреля 1942 года на самолете Пе-8 совершил 28 боевых вылетов на бомбардировку военно-промышленных объектов в глубоком тылу противника, в том числе Берлина, Кенигсберга. Дважды ранен в боевых вылетах. В мае 1942 года капитан Александр Штепенко в качестве штурмана экипажа (командир майор Пусэп Э. К., второй пилот капитан Обухов В. М., второй штурман капитан Романов С. М.) на бомбардировщике ТБ-7 (Пе-8) участвовал в выполнении правительственного задания по доставке советской делегации во главе с наркомом иностранных дел СССР В. М. Молотовым в Англию и США через Германию, Северное море, Атлантику, с промежуточными посадками в Шотландии, Исландии и Канаде.
Указом Президиума Верховного Совета СССР от 20 июня 1942 года за выполнение особо важного правительственного задания и за образцовое выполнение боевых заданий командования на фронте борьбы с немецко-фашистским захватчиками и проявленные при этом мужество и героизм майору Штепенко Александру Павловичу было присвоено звание Героя Советского Союза.
Всего на Пе-8 Штепенко совершил 78 успешных боевых вылетов. 31 декабря 1942 года был награжден орденом Отечественной войны I степени. С июня 1943 года и до конца войны подполковник Штепенко — старший помощник начальника инспекции 18 воздушной армии по штурманской службе: обучал штурманов, разрабатывал программы по их обучению. 28 мая 1945 года награжден орденом Александра Невского. После войны продолжал службу в ВВС СССР. С 1955 года в запасе.