Фамилия Кострубко звучит по-украински, и это первая зацепка. Суффикс -ко — характерный уменьшительный или патронимический формант для украинских и белорусских фамилий (сравните: Шевченко, Гончаренко, Бойко). Он указывает на то, что прозвище Коструб — основа — принадлежало отцу или старшему родственнику, а потом перешло к потомкам в форме «маленький Коструб» или «сын Коструба».

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

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

География фамилии подтверждает украинское происхождение. Кострубко чаще всего встречается в центральных и восточных областях Украины (Черкасская, Полтавская, Киевская), а также в приграничных районах России, куда переселялись украинцы. Среди казацкой старшины эта фамилия не зафиксирована — скорее, она бытовала среди крестьян и мещан.

В русском контексте фамилия могла писаться и как Кострубков (с русифицированным суффиксом -ов), но форма на -ко сохранилась именно как маркер украинского происхождения. Если ваш предок носил фамилию Кострубко, он почти наверняка происходил из украинской среды, и его предка прозвали за сухощавость, связь с костром или обрядовую внешность.