Deuce, that's a great back-story.
Would the Conan "yarns" be themselves the body of the Nemedian Chronicles?
That's a puzzler. The Irish Nemedians were, ultimately, of the same blood as the Gaels according to the Lebor Gabala (the Irish "Book of Invasions"). In fact, just about every ethnic group that settled in Eriu, from the Partholonians on, were related to the late-coming Gaels (according to the "LG"). Not coincidentally, REH has the Nemedians be of partial Cimmerian descent. The Irish are renowned for their attachment to the tales of their heroes and for their obsession with preserving Irish history. Perhaps the Irish Nemedians had carried the tales of the mighty Cimmerian all the way from Scythia ("Cimmeria East")? However, there is the reference to Conan within the "Chronicles" excerpt.
Patrice Louinet has an interesting theory that "Phoenix" may have started as an "Allison/reincarnation"-type of yarn (while using the plot of "Axe"). Hard to say. We know from several accounts that there were books in Ireland before the Christian conversion. In the "LG", I believe that the Nemedians passed through Greece. Might they have picked up "Linear B" script? So, we might have an instance where the Irish scholar (perhaps claiming Nemedian blood) tells the young prince that there was once a mighty kingdom where Deutschland now lay. It too fought enemies from the north, east and west. Perhaps the scholar's tales were more along the lines of The Hyborian Age. Perhaps REH "remembered" the Conan yarns (as in the first line of Cimmeria). Ol' von Junzst could have been living and reading the "Chronicles" where Nemedia itself once was. As I said, lots of possibilities.
Another thing, I think that the Cimmerians were already there when the Nemedians arrived, no?
The sequence of events in the "LG" goes something like this...
Shortly after the Flood, Partholon settles with his people in Ireland. They are followed by Nemed and his followers,who wage war against the diabolical Fomorians. The Fomorians are led by King Conand the Fomorian. The Nemedians triumph, but Fomorian sorcery calls up an inundation which scatters the surviving Nemedians to various points hither and yon. The Nemedians return as the Fir Bolg (and the Fir Domnann and the Fir Galeoin). They are displaced by the Tuatha de Danaan, whom Howard explicitly calls "Cymric" (Brythonic) in "KotN". Finally, the Sons of Mil ("Milesians"/Gaels/descendants of the Cimmerians) sail from Galicia in north-western Spain and wrest the isle of Erin from the Tuatha de Danaan in an epic battle. Howard seems to have felt pretty strongly about the issue of "Cymric/Brythonic" precedence in Ireland. The first letter he wrote to Lovecraft was about that very topic.
BTW, one of the sons of Nemed was named Artur.