Родился в селе Верба Черниговского округа Украинской ССР. В возрасте 17 лет был призван на службу в ряды РККА. Учился в полковой школе младших командиров. С 4 июня 1944 года сражался на 3-м Украинском фронте.

Гвардии младший сержант Петр Старовойтов в составе 3-й стрелковой роты 1-го мотострелкового батальона 3-й гвардейской ордена Ленина механизированной бригады 1-го гвардейского механизированного ордена Ленина, ордена Кутузова корпуса освобождал Будапешт и Вену.

В боях за Вену (16 марта-15 апреля 1945 года) корпус сражался в условиях сильно укреплённого крупного европейского города. В одном из боев был убит командир отделения, где служил Старовойтов. Петр Наумович взял на себя командование, и умело повел солдат в бой. За время наступательных боев отделение под командованием Старовойтова уничтожило 20 гитлеровцев, пленило 32 фашиста, сожгло 3 машины с оружием. 29 апреля 1945 года Петр Наумович был награжден орденом Красной Звезды.

Победу гвардии младший сержант Петр Старовойтов встретил в предгорьях Австрийских Альп. За отличие в боях за Вену и Будапешт награжден медалями «За взятие Будапешта» и «За взятие Вены».

Когда закончилась война, Петр Наумович продолжал служить еще 5 лет на Кавказе и в Средней Азии.

После войны проживал в селе Терентьевском Прокопьевского района. Более тридцати лет работал бурильщиком в Левобережной геологоразведочной партии. За высокий профессионализм удостоен звания «Отличник разведки недр».