Si buscas el primer rey sin haber pruebas arqueológicas supongo que habría que entrar en un debate antropológico e incluso léxico, para dilucidar quién se consideró o qué pueblo consideró primero a su líder como un rey.
Si miramos cualquier tribu de las que extraemos teorías sobre la vida en la edad de piedra, tenemos que la luchas entre las diferentes tribus daban lugar a anexiones y ésto al gobierno por parte del jefe vencedor a la tribu anexionada. El gobierno de diferentes tribus anexionadas daría lugar a una especie de pseudo-reinado en miniatura.
pero si buscas al primer rey datado, creo que deberías fijarte en los sumerios, que si no recuerdo mal inventaron la escritura, o por lo menos es el pueblo más antiguo del que conservamos escritura. Por ahí creo que existe una lista de reyes, algunos de ellos según los historiadores poco creíbles debido a su datación.