Родился 11 февраля 1917 в с. Явленка ныне Есильского района Северо-Казахстанской области в семье крестьянина. Русский. Окончил начальную школу. Работал шофером пожарной части г. Сватово Ворошиловградской области, затем мотористом на железной дороге. В армии с 1941 года.
Участник Великой Отечественной войны с 1941. В 1942 окончил курсы младших лейтенантов. Минометный взвод 878-го стрелкового полка (290-я стрелковая дивизия, 50-я армия, 2-й Белорусский фронт) под командованием старшего лейтенанта Коваленко 28 июня 1944 первым пробился на окраину Могилева. Когда кончились мины, бойцы взвода в рукопашной схватке захватили батарею 122-мм минометов и отразили контратаку противника. Звание Героя Советского Союза присвоено 24 марта 1945.
За годы войны Павел Коваленко был одиннадцать раз ранен и один раз контужен.
С 1946 года капитан П.В. Коваленко — в запасе. Вернулся в город Сватово. Работал заведующим гаражом на масло-экстрактном заводе № 7. Однако на заводе ему пришлось работать недолго. Фронтовые раны все чаще напоминали о себе. Здоровье ухудшалось, и 24 августа 1949 года на 33-м году жизни Герой Советского Союза П.В. Коваленко скончался… Похоронен в центре города Сватово, на площади Первого мая.
Награжден орденом Ленина, орденом Красного Знамени, орденом Александра Невского, орденами Отечественной войны 1-й и 2-й степени, орденом Красной Звезды, медалями.
Именем Героя названа улица в Сватово. На доме, где жил П.В. Коваленко, и на здании завода, где работал, установлены мемориальные доски. Имя Героя значится среди 8 Героев Советского Союза — сватовчан на мемориале Славы, Памяти и Скорби.