Родился в 1783 г. В 1803 г. Полешко был произведён в подпоручики 1-го егерского полка. 27 января 1807 г. за участие в Прейсиш-Эйлаусском сражении награждён золотым крестом; в том же году, 16 марта, был произведён в поручики, а 24 мая пожалован орденом св. Анны 4-й степени; 16 сентября 1808 г. Полешко был пожалован орденом св. Владимира 4-й степени с бантом, 16 августа 1810 г. — произведён в штабс-капитаны.
6 сентября 1811 г. Полешко был переведён в лейб-гвардии Егерский полк, с которым принял участие в Отечественной войне. Здесь 12 декабря 1812 г. он был награждён золотой шпагой с надписью «За храбрость», 5 июня 1813 г. — орденом св. Анны 2-й степени, 15 июля того же года был произведён в капитаны, 15 сентября — пожалован алмазными знаками к ордену св. Анны 2-й степени, 30 ноября произведён в полковники.
15 января 1814 г. Полешко был назначен полковым командиром 34-го егерского полка. 9 марта 1814 г. пожалован пожалован орденом св. Владимира 3-й степени, 18 числа того же месяца и года за отличие при взятии Парижа — орденом св. Георгия 4-го класса (№ 2885 по списку Григоровича—Степанова).
17 апреля 1822 г. был произведён в генерал-майоры с зачислением командиром 3-й бригады 5-й пехотной дивизии, 9-го июня того же года назначен командиром 2-й бригады 17-й пехотной дивизии и 30 января 1827 г. — 1-й бригады 18-й пехотной дивизии.
С 3 мая по 3 июня 1828 г. Полешко участвовал в осаде крепости Браилова, 25 июня пожалован орденом св. Анны 1-й степени, 8 июля того же года был в сражении под крепостью Шумлой. 7 сентября за отличие в делах против турок награждён золотой шпагой, украшенной алмазами, и алмазными знаками к ордену св. Анны 1-й степени, а 23 сентября того же 1828 г. назначен командиром лейб-гвардии Егерского полка.
За отличия, оказанные в войну 1831 г. с польскими мятежниками, Полешко 25 июня 1831 г. получил орден св. Георгия 3-й степени (№ 426)
В том же 1831 году произведён в генерал-лейтенанты и 22 августа 1831 г. назначен командиром 4-й гвардейской пехотной бригады. Награждённый в 1836 г. орденом Белого Орла, Полешко состоял командиром 2-й гренадерской дивизии.
Умер в ночь с 7 на 8 декабря 1837 г. в Пскове, похоронен там же на Дмитриевском кладбище.