Okay, how about this: the Asguhstas and the M'azael were originally part of the same proto-nation (like the Celts all being the same 'nation', but still operated in different kingdoms). Then there was a war; I suggest that the M'azael had split off from the religion the Asguhstas had pre-Baruk conquest, and this created a schism between the two that eventually escalated to war. The M'azael lost and were forced into exile in the far north, humiliated and almost wiped out by the war.
Some time later (I was thinking around the time the M'azic Empire- the precursor to my Solaran Administration- started dividing into separate states) a new religious order is founded. They believe in Kherem, as all M'azael do, but in their dialect he's called Kharam (slowly bastardised down to Kharum). They are led by a man called Allahanael Am-Habahlliel of the Baruk tribe. One of their core beliefs is that the M'azic people had been deprived of their holy land when they were exiled, and that they must seek vengeance against those who cast them out. They gather together many tribes and ride south into their holy land, and after much bloodshed conquer the Asguhstas.
As they start to absorb into the Asguhstas culture (and start converting people to their religion), names change to suit Asguhstas pronounciation- hence Allahanael Am-Habahlliel becomes Allahani Am-Habahlla, and Kharam slowly changes to Kharum.
This would neatly fill out the back stories of both of our nations, as well as providing a healthy dose of idealogical hatred between our two cultures. What do you think?