you would have to pit the predator against a mythical character, otherwise, its just the same old story of evil space monster vs puny human, human wins. Same story, different setting. You might gain some leverage using Beowolf or Hercules, but unless the writer can produce something creative and new, the audience isn't really going to care. At least with Predators, it was set on a different planet and had different types of predators, but it was still a rehash of the first movie.
I personally can see a story like this as a comic book, but I can't see the studio willing to put money into another predator movie unless the script is new and fresh. I fail to see where setting the predators into the medieval times would add anything to the franchise.