Фамилия Старовойтенко — яркий пример украинской модели образования фамилий, где суффикс -енко указывает на происхождение по отцу: «сын Старового» или «потомок Старового». Это одна из самых распространённых фамильных моделей в Украине, особенно на Левобережье и в южных регионах. В отличие от русских фамилий на -ов/-ев, украинские на -енко не склоняются по падежам в мужском роде и не имеют женского варианта.

Основа фамилии — прозвище Старовой. Оно сложное, состоит из двух корней: «старый» и «вой» (от «воин»). Прозвище Старовой могли дать бывалому, опытному воину, ветерану, который прошёл не одну кампанию. В казацкой среде, где боевой опыт ценился превыше всего, такое прозвище звучало уважительно. Встречается и более прозаичное объяснение: «старый» могло означать не возраст, а «прежний», «бывший» — например, бывший воин, отошедший от дел.

Менее вероятная, но возможная версия связывает фамилию с топонимом — селом или хутором с названием Старовойтово (такие есть в Черниговской и Сумской областях). В этом случае родоначальник получил фамилию не по прозвищу, а по месту жительства или выхода. Но для фамилий на -енко первична всё же патронимическая модель от личного прозвища.

Интересная деталь: фамилия Старовойтенко — не самая частая среди «военных» фамилий на -енко. Куда распространённее Старовойтов (русский вариант) и Старовойт (украинский, без суффикса). Форма на -енко встречается реже и указывает на более позднее закрепление фамилии, когда модель «сын такого-то» уже стала доминирующей. Носители фамилии традиционно сосредоточены в центральной и восточной Украине, а также в южных областях России, куда шли миграционные потоки из Малороссии в XVIII–XIX веках.

Разбирая фамилию по составу, получаем: корень «стар» + соединительная гласная «о» + корень «вой» + суффикс «т» (как в словах «воевода», «воин») + суффикс «енк» + окончание «о». Суффикс «т» в основе «старовойт» — редкий словообразовательный элемент, который придаёт прозвищу оттенок деятеля: Старовойт — это тот, кто «старо воюет», то есть давно и много.