The samurai are nice, but a bit incongruous. I think that they make a nice addition stylistically, but seriously-- samurai in late medieval Western Europe?
However, if you have an idea about incorporating this story-wise, I think you've got a lot of potential. If I might, I have an idea that may work, and would sort of be historically possible.
Christianity did not fare too well in Japan, especially after a bunch of converted samurai got uppity, revolted, and were (if memory serves) were crucified for their trouble. In Dukes&Mercs' equivalent, let a similar event, involving a similar culture and similar religion happen. However, in D&M-land, one lord who had converted backed out of the revolt, converted back, and left his religious comrades in the lurch. His men, however, had embraced the new ways more zealously than their masters, and abandoned him; their devotion to their new faith outweighed their devotion to a cowardly pagan man. Knowing that they'd find no peace in their native land, they set out for a country where they could practice their religion. Upon arriving in a land just as war-torn as the one they had just left, many of them began hiring themselves out as mercenaries.
The story could be related by one of the exiles; the obvious choice would be a samurai (the abandoned lord's bodyguard, perhaps), but I personally prefer the idea of a Japanese priest, armed with a staff and high healing skills.
Edit: of course, Calradia being Calradia, Christianity would be somewhat incongruous itself. Perhaps the narrator could refer to the religion that "your priests" brought over.
On another note, it's been a while since I've messed around with modding, but as far as I can recall it's pretty easy to modify stats and equipment. If I could have your permission and the relevant models, could I try to make a version of D&M with firearms? I realize you must have a good reason for removing them, but I liked them.