Павел Павленко родился в Киеве. Его отец, оперный актер, в 1903 году переехал на постоянное место жительства в Москву и перевез с собой семью.
В 1912 году Павел поступил на учебу в XI Московскую гимназию, а после революции перешел в 109-ю советскую школу, окончив которую в 1920 году, начал свою трудовую деятельность в качестве сценариста в Московском украинском театре «Студия». Здесь же Павленко впервые вышел на сцену, сыграв свои первые роли, среди которых были Возный («Наталка-Полтавка»), Сених-ага («Запорожец за Дунаем»), Омельков («Мартын Боруля») и другие. Затем, с лета 1922 года по осень 1923 года, Павел работал в свободно-показательной труппе Подива-14.
В 1923 году Павел Павленко поступил на актерский факультет Московского государственного театрального техникума имени Луначарского, где учился до 1926 года и одновременно, с сентября 1924 года, работал в Московском театре для детей. В октябре 1927 года Павленко перешел во вновь организованную в Москве профклубную мастерскую при Управлении академическими театрами, а в 1928 году на два сезона уехал работать в Харьковский краснозаводской театр.
В октябре 1930 года Павел Павлович вернулся в Москву и вступил в труппу Театра Революции, где оставался до 1932 года. Здесь актером были сыграны Весельчак («Первая конная»), Власенко («Двенадцатые»), судья («История одного убийства»), Рапуткин («Человек с портфелем») и другие роли.
Последующие шесть лет творческая судьба Павла Павленко была связана с именем Юрия Завадского. Сначала он был актером его театра-студии, а затем, с 1936 по 1938 годы, вместе с ним уезжал работать в драматический театр имени Горького в Ростов-на-Дону. За этот период Павленко были сыграны Кристи («Ученик дьявола»), Бриден («Любовью не шутят»), Прищемихин («Опыт»), Шапелев («Школа неплательщиков»), Пикалов («Любовь Яровая»), Левшин («Враги») и другие роли. Здесь же Павленко попробовал свои силы в качестве режиссера, поставив спектакль «Как закалялась сталь».
Вернувшись из Ростова, Павел Павлович стал актером Центрального театра транспорта, где работал до 1944 года и сыграл много заметных ролей, среди которых: Шмага («Без вины виноватые»), Колечко («Сын народа»), Агафонов («Со всяким может случиться»), Расплюев («Свадьба Кречинского»), Мамонтов («Накануне»), Забудько («Дым отечества») и другие.
В 1944 году Павел Павленко по приглашению Завадского перешел работать в Театр имени Моссовета, где оставался до 1947 года. Затем один сезон играл в Театре оперетты, а в декабре 1948 года вновь вернулся в Центральный театр транспорта, где был одним из ведущих актеров вплоть до ухода на пенсию в 1960 году.
Уже с первых выступлений на сцене Павленко заявил о себе как об интересном характерном актере, игравшем ярко и с большим юмором. Со временем мастерство актера стало еще более совершенным, что он наглядно продемонстрировал в период работы у Завадского и в Театре транспорта. Павленко фактически не играл главных ролей, оставаясь непревзойденным мастером эпизода и ролей второго плана. При этом актер никогда не терялся за спинами главных героев, превращая свои маленькие роли в настоящие шедевры.
В кино актер пришел уже зрелым мастером и сразу же занял там свою нишу, играя роли всевозможных старичков – от скромных и застенчивых до веселых и задорных. Настоящей удачей для Павленко стала встреча с режиссером Александром Роу, в сказках которого актер сыграл свои лучшие роли в кино – главнейшего церемониймейстера в «Королевстве кривых зеркал», старика-отца в «Морозко» и Водяного царя в «Огонь, вода и… медные трубы». Членам съемочных групп этих картин он запомнился как веселый и остроумный человек, не терявшийся в больших компаниях, всегда находивший добрые слова в адрес своих коллег.
Павел Павленко был женат, но детей у него не было. После 1976 года он не снимался и как прожил свои последние годы, к сожалению, неизвестно. Очень жаль, что никто не поинтересовался этим при его жизни. Он дожил до солидного возраста и умер, всеми забытый.