Родился 14 января 1914 года в селе Берестовец ныне Борзнянского района Черниговской области Украины в крестьянской семье. Украинец.
Образование неполное среднее - окончил 7 классов. После школы работал счетоводом в Комаровском райземотделе.
В 1936 году Нежинским райвоенкоматом Черниговской области Украинской СССР призван в Красную Армию.
После окончания в 1940 году Тбилисского артиллерийского училища был направлен для прохождения службы в Ленинградский военный округ. Принимал участие в Советско-финской войне. После финской кампании преподавал в Подольском артиллерийском училище.
С января 1942 года в действующей армии - командир миномётной батареи, дивизиона 815-го артиллерийского полка 272-й стрелковой дивизии 7-й армии Карельского фронта. Активный участник обороны Карелии и боев в районе Подпорожье - река Свирь. Был дважды ранен.
Звание Героя Советского Союза майор Павел Иллюшко получил «за образцовое выполнение боевых заданий командования на фронте борьбы с немецко-фашистским захватчиками и проявленные при этом мужество и героизм» в ходе Свирско-Петрозаводской наступательной операции: в первый день наступления, 21 июня 1944 года, перед началом форсирования реки Свири в районе Лодейное Поле главными силами командование фронта и армии решило дополнительно уточнить систему огня финнов. Для этого была создана группа из молодых бойцов-добровольцев. Замысел оправдался. При преодолении реки группой смельчаков противник открыл ожесточённый огонь. В результате были обнаружены многие его огневые точки. Несмотря на продолжавшийся обстрел, группа добралась до противоположного берега и закрепилась на нём. Своими самоотверженными действиями герои способствовали успешному форсированию реки главными силами. За героический подвиг все 16 воинов были удостоены звания Героя Советского Союза. Вместе с воинами-пехотинцами в числе первых переправился через Свирь отважный офицер-артиллерист. Вместе с пехотинцами он ворвался во вражеские траншеи, где оборудовал свой передовой наблюдательный пункт и, лично корректируя огонь дивизиона, подавлял огневые точки противника.
23 июня 1944 года советские части были остановлены перед второй полосой обороны противника, у деревни Сармяги Олонецкого района Карелии. Укрепления этого узла сопротивления были построены за топким болотом, заранее пристрелянным огнём пулемётов и артиллерии. Майор Иллюшко скрытно развернул свой НП в пятидесяти метрах от вражеских укреплений и, тщательно разведав огневую систему противника, обеспечил подавление вражеских огневых средств. Вместе с атакующей пехотой Иллюшко вновь одним из первых ворвался в траншеи противника, а когда был убит командир 2-го стрелкового батальона капитан Шмаков, принял на себя командование батальоном. Бой закончился полным разгромом вражеского гарнизона в Сармяги.
Указом Президиума Верховного Совета СССР от 21 июля 1944 года майору Иллюшко Павлу Ивановичу присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда» (№ 3827). О присвоении звания Героя, Павел Иванович узнал в госпитале, где находился после тяжёлого ранения, полученного при штурме города Питкяранта.
Войну Иллюшко Павел Иванович закончил на Дальнем Востоке в составе войск 1-го Дальневосточного фронта после разгрома Квантунской армии и освобождения восточных районов Маньчжурии, Ляодунского полуострова и северной Кореи.
В 1945 году он окончил Ленинградскую высшую офицерскую артиллерийскую школу. Служил в артиллерийских частях Советской Армии. С 1950 года в запасе, затем в отставке. Жил в городе Кировск Мурманской области. Умер 12 февраля 1996 года.