Just to clarify your question, when you say "any middle ages nation" do you mean "any random one of them," as in, say "could the Kingdom of Hungary or the Buyids have sailed to the new world?", or do you mean would it have been possible for, say, the single most advanced among them to have sailed to the new world?

If you mean the latter, of course, Europeans in the Middle Ages did sail to the New World, as we know from the discovery of Norse sites in Newfoundland.