'But some day a man will rise and unite thirty or forty clans, just as was done among the Cimmerians, when the Gundermen tried to push the border northward, years ago.'
REH, Beyond the Black River
He didn't say someone united the whole nation, just a fair number of clans. Cimmeria is large enough to hold far more clans than forty.
North of Aquilonia, the westernmost Hyborian kingdom, are the Cimmerians, ferocious savages, untamed by the invaders, but advancing rapidly because of contact with them; they are the descendants of the Atlanteans, now progressing more rapidly than their old enemies the Picts, who dwell in the wilderness west of Aquilonia.
Robert E. Howard, The Hyborian Age
Clans of ferocious savages rarely have a united kingdom.
The country claimed by and roved over by his clan lay in the northwest of Cimmeria, but Conan was of mixed blood, although a pure-bred Cimmerian. His grandfather was a member of a southern tribe who had fled from his people because of a blood-feud and after long wanderings, eventually taken refuge with the people of the north.
Robert E. Howard, Letter to P.S. Miller
The clans of Cimmeria have blood-feuds with each other, another piece of evidence against a unified country.
'I never saw another Cimmerian who drank aught but water, or who ever laughed, or ever sang save to chant dismal dirges.'
'Perhaps it's the land they live in,' answered Conan. 'A gloomier land never existed on earth. It is all of hills, heavily wooded, and the trees are strangely dusky to that even by day all the land looks dark and menacing. As far as a man may see his eye rests on the endless vistas of hills beyond hills; the skies are nearly always gray. Winds blow sharp and cold, driving rain or sleet or snow before them, and moan drearily among the passes and down the valleys. There is little mirth in that land.'
'Little wonder men grow moody there,' quoth Prospero with a shrug of his shoulders, thinking of the smiling sun-washed plains and blue lazy rivers of Poitain, Aquilonia's southern-most province.
'Strange and moody, indeed,' answered Conan. 'Life seems bitter and hard and futile. The men of those dark hills brood overmuch on unknown things. They dream monstrous dreams. Their gods are Crom and his dark race, and they believe the ghosts go wailing forevermore. They have no hope here or hereafter, and they brood too much on the emptiness of life. I have seen the strange madness of futility fall upon them when a little thing like a spinning dust cloud, or the hollow crying of a bird, or the moan of the wind through bare branches brought to their gloomy minds the empiness of life and the vainness of existence. Only in war are the Cimmerians happy.'
Robert E. Howard, The Phoenix on the Sword (draft)
Since the Cimmerians are elsewhere described as raiding occasionally into Pictland, Gunderland, Hyperborea, and Nordheim (and explicitly said not to be a war), then these wars must be inter-tribal, which again implies the lack of a unified king.
Keep in mind, that same document you are using indicates kings of Asgard and Vanaheim, which are also contra-indicated in the stories.
'Tall and fair and blue-eyed. Their god is Ymir, the frost giant, and each tribe has its own king. They are wayward and fierce. They fight all day and drink ale and roar their wild songs all night.'
R. E. Howard, The Phoenix on the Sword (I did the underlining for emphasis)
Also he indicates Brythunia was to the south of Aquilonia, which is something else he later changed. I think it is best to regard that document as evidence of brainstorming, but not canonical information.
That said, it is your campaign, and if you want a Cimmerian king, go for it!
