The issue isn't how old is the *story* of "King Orfeo," or what they might have done with it in the Middle Ages. The issue is how old is the British *ballad*.

The answer is unknown.

Donald S. Taylor offered the suggestion that, based on a possible twelfth-century allusion, that "Sir Aldingar" in one form or another was the oldest Child ballad.

That was sixty years ago, and nobody, AFAIK, has challenged Taylor's evidence - though there's not quite enough of it to prove that he was right.