I don't think anything besides a modern game would work, especially considering how war is conducted. Medieval warfare was extremely traditional, and involved sieges, and most of the time, was not for land grabs. Which means that combat
will be even slower than it is now, with just taking a province. I can easily compare this to two Paradox games, if we go Medieval, we'd have to do sieges EU style, where it takes so many days for a city to succumb to hunger and give up. Or if we go Medieval, we'd have to do combat HOI style, where if an army goes into an enemy province, it takes the enemy province. And considering how slow the combat was just taking provinces, imagine how long it would take if we had to factor siege into it too...