Фамилия Кононенко — типичный пример украинской модели образования фамилий на -енко, которая в XIV–XVII веках распространилась по всей территории современной Украины. Суффикс -енко буквально значил «сын», «потомок» или «ученик», поэтому фамилию стоит понимать как «сын Конона». В основе лежит крестильное имя Конон, которое пришло на Русь из греческого языка вместе с христианством. Греческое «конон» означает «трудящийся» или «трудолюбивый», так что предок носителя этой фамилии, скорее всего, получил имя с пожеланием быть работящим человеком.

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

Интересно, что в русской традиции та же основа дала фамилию Кононов, а в польской — Кононович. Разные суффиксы указывают на то, в какой этнической или социальной среде закрепилось родовое прозвище: -енко — это маркер украинского происхождения, тогда как -ов и -евич типичны для великорусских и шляхетских родов соответственно. Таким образом, по одной только форме фамилии можно с уверенностью сказать, что её носители — выходцы с украинских земель, где подобные патронимы стали массово оформляться в казацкую эпоху.