I could see maybe playing upon the religious oppression of the time, and having the Predator seen, once again, as a demonic figure. Having him appear in a medieval church setting like an invisible specter, warping a cross behind him. Having someone seeing themselves as having "brought the curse" and being "in league" with the creature, only to later be killed by it unceremoniously.
But as far as to where it would lead? I mean, that's all this ever feels like to me. Let's take the Predator and stick them in a new setting... and ultimately just end up redoing the same things we've already seen and experience, with a slight twist. A very slight twist.
I mean, if you wanted to do it, you'd have to be really creative, hit at just the right time (when historical-theme movies were back in high popularity, for example.) and really sell it, because it's not exactly a main stream idea. People like urban settings, they like war zones, they like seeing modern day fighting men (Or even futuristic ones) fighting a creature like the Predator... Because, let's be honest. Nothing that existed in the Roman Era, or Medieval times, would stand a chance against a Predator. Nothing man portable, anyway. Cross bows, arrows, spears. Maybe some axes or swords, but i'd venture a guess the predator could cut those to pieces very easily.