Павленко попал в стан красно-белых в 2001 году возрасте 16 лет, перейдя из молодёжного состава «Лозанны», и свой путь во взрослом футболе начинал под руководством Олега Романцева. Тогда в команде ещё играли Титов, Бесчастных, Парфёнов, Булатов… В том же году он дебютировал за красно-белых и принял участие в пяти матчах в чемпионате, в котором «Спартак» завоевал свои последние на данный момент золотые медали.
Красно-белый путь получился для Павленко очень непростым. Осенью 2002 года «Спартак» провалился в группе Лиги чемпионов, потерпев рекордные шесть поражений из шести с разницей мячей 1-18, но на общем фоне Александр смотрелся очень недурно. Возможно, именно это помогло ему в 2003 году получать больше игровой практики – если в первые два сезона он проводил за «Спартак» не более 10 официальных игр за сезон, то тут сыграл уже 30 – и это с учётом 5-матчевой дисквалификации в чемпионате России. Естественно, болельщики возлагали на него всё больше надежд.
Можно сказать, что 2003 год стал пиком карьеры Павленко в «Спартаке» — играл он очень неплохо, а в Кубке УЕФА смог отметиться двумя голами, один из которых, забитый «парашютом» в ворота бухарестского «Динамо», смотрелся невероятно красиво. Карьера молодого полузащитника шла по нарастающей, а в сезоне-2004 у многих появилась надежда, что он даже сможет стать достойной заменой Егору Титову, который получил годовую дисквалификацию. Однако ожиданиям болельщиков сбыться было не суждено: сезон Александр провёл достаточно блекло и заменить ключевого игрока спартаковской полузащиты не смог.
Сезон-2004 стал переломным для карьеры Павленко в «Спартаке»: если до этого дела его шли всё лучше и лучше, то затем пошли на спад. Последующие два года были испорчены травмами, а в 2007 году начались скитания Павленко по арендам. «Спартак» решил, что в том сезоне услуги Александра ему не пригодятся, и Павленко оказался в первом дивизионе, где стал одним из ключевых игроков «Шинника» и помог ярославскому клубу вернуться в Премьер-Лигу.
После возвращения Александра из аренды в сезоне-2008 Станислав Черчесов решил предоставить Павленко второй шанс, оставил Александра в команде и регулярно выпускал в стартовом составе. Результат не заставил себя долго ждать: он выступал на высоком уровне и доказал, что по праву занимает место в основном составе красно-белых. Павленко даже вошёл в расширенный список сборной Гуса Хиддинка на Евро-2008, но в число 23 игроков, отправившихся на финальную часть турнира, не попал. В итоге сезон испортила травма, которую уроженец Украины с российским паспортом получил сразу после летней паузы – вскоре он вернулся на поле, однако вторая часть сезона получилась для него совсем неудачной.
После ухода Черчесова Павленко не смог закрепиться в составе ни у Микаэля Лаудрупа, ни у Валерия Карпина и летом 2009 года снова отправился в аренду — в «Ростов». В донском клубе Павленко зарекомендовал себя очень неплохо, уже в дебютном матче – против ЦСКА – отдал голевую передачу, а всего в девяти матчах забил три гола.
По окончании сезона Александр вернулся в расположение «Спартака» и надеялся, что ему вновь предоставится шанс побороться за место в основе, однако у Карпина был другой взгляд на ситуацию, и в итоге «Ростов» с радостью снова арендовал Павленко. За 2010 год он провёл в их составе 24 игры – втрое больше, чем в сезоне-2009, но забил всё те же три гола, зато раздал 5 голевых пасов и в целом был важным игроком для «Ростова», больше половины игр чемпионата начав в стартовом составе.
После завершения арендного соглашения Павленко снова вернулся в «Спартак», но достаточно скоро стало ясно, что и на сей раз ему не выпадет шанса пробиться в состав. Было объявлено, что на предсезонный сбор со «Спартаком» полузащитник не поедет, а клуб будет искать ему новое место работы.
Павленко – единственный из состава «Спартака» 2001 года, кто до сих пор находится в команде. Его спартаковская карьера начиналась примерно в одно время с Дмитрием Торбинским, Дмитрием Сычёвым, Павлом Погребняком, Александром Самедовым – все они уже давно играют за другие команды, а Александр до сих пор в «Спартаке». Правда, за это время провёл лишь чуть более сотни игр в чемпионате. Трижды он отправлялся в аренду, несколько раз ему выпадал шанс закрепиться-таки в составе московского клуба, однако воспользоваться ими в силу разных причин Александр так и не сумел.
Тем не менее похоже, что искать, куда трудоустроить полузащитника, «Спартаку» долго не придётся – заинтересованность в Павленко проявил «Терек». Ещё не ясно, хотят ли грозненцы взять его в аренду или выкупить, но сам Александр уже заявил, что был бы рад играть в клубе, который накануне возглавил Рууд Гуллит. Если переход состоится, то легко Павленко точно не будет – зато к когорте тренеров, с которыми он работал (а это такие специалисты, как Романцев, Скала, Старков, Федотов, Лаудруп, Черчесов, Карпин, Долматов и Протасов) добавится ещё одно имя – да ещё какое! Нам же остаётся лишь пожелать Александру удачи в этом приключении.
С днём рождения!