Вопрос упирается в то, что считать "Главой государства" и что считать "выборами". Если принять достаточно строгие определения обоих терминов, ответ действительно не тривиальный.

Польская элективная монархия (с 1573 года, после Генриховых артикулов) - сильный кандидат, но там голосовала только шляхта (около 10% населения), а не граждане. Это скорее аристократический консенсус.

Выборы папы конклавом - тоже не совсем государство в современном смысле, хотя Папская область была полноценным политическим образованием.

По академическому консенсусу первыми выборами именно главы светского государства с относительно формализованной процедурой называют американские президентские выборы 1788-1789 годов. Коллегия выборщиков, конституционно закрепленная процедура, светский характер - это принципиально отличает их от средневековых прецедентов.

Оговорка: "всеобщих" они не были - голосовали только мужчины-собственники, рабы не голосовали. Первые прямые всеобщие президентские выборы с широким избирательным правом - это уже совсем другая история и другой век.

По польской элективной монархии добавлю: первые выборы там фактически прошли в 1573 году (Генрих Валуа), но сам принцип выборности польских королей закрепился еще с 1386 года (выборы Ягайло). Масштаб шляхетского представительства в 1573 году был огромным по меркам эпохи - съезды под Варшавой собирали десятки тысяч человек. Некоторые историки именно это считают первым прецедентом массовых выборов руководителя государства.