Well. if they are a common medieval county they should have their grain transported with them. It seems to me that the time travel thing would pick up anything human built/manipulated and as such grains and at least cows would come back with them. They'd likely have enough grain to last them up to 8 years.
Let's assume they're English and as such are always going to be either on English soil of French soil, or near enough...let's also make this easy and say they're from 1000 CE, smack dab in the middle of the Medieval period.
The first period we look at is the 1 CE. Do they survive?
Supposing that that they are far enough in they should last a few generations and maybe till present day if they are all the way to the North, but too far south and they'll survive only between 30 and 200 years as their own place due to Roman invasion. I bank on the Romans winning even with better fortifications than those surrounding them, that just makes them a larger target. Other than that they should easily be able to continue living as they were. They would have to learn older languages and build up alliances for whatever, but other than that they'd be fine.
The next period we'll jump to is 11,000 BCE.
Depending on how bad the Late Glacial Maximum really was and how far it extended, them getting put here, they'd be dead within a few months more than likely, or be perfectly capable of survive. The largest issues they would face once they fixed their shelters to be more warm is setting up farm land which at this point in history Europe was more or less unsuitable for it, and mining which would only really take time and you can assume some village should have mining equipment and be right over some place they can mine so that isn't so much an issue. If farming failed there should still be plenty of large game in the area and Medieval humans should be able to easily over power most of them in that region.
100,000 years ago... They'd be dead very shortly due to the ice age.
1,000,000 years ago...
We're talking about a situation much like the 11,000 BCE one. There aren't many issues. There is evidence of Human in england in this period so assuming they have their grain stock or are able to find game animals, which they sould be able to there isn't a problem here.
10,000,000 years ago and beyond...
At some point the issue isn't the base ability to survive against the elements, but rather that the animals become just to fierce to handle. Humans lived with Terrorbirds and Mega-Mammalian Fauna. The Latter we know wouldn't be problematic, but the terrorbirds would likely tear humans apart, armored or not, especially with the armor that our humans would have. Keep going further back and the greater the likelihood of running to something horific that just can't be survived against up until just before the extinction of the dinosaurs which is harder to survive during due to the environment and all the animals going extinct. That seems to be the limit in my mind about how far back in time humans could reasonably survive from that period of time... Before that time period it's nightmare after nightmare in the fauna and floura.
We're talking animals that today kill us in a single sting or are pests or annoy us with bites and are just a few inches long at most... Now scale those up to a meter or 2. Or look in the ocean and find things that make great white sharks look like guppies. Every time period before this point has some crazy issue.
There is a period that I forget it's name that humans might have a chance in which is the period when mammal like reptiles were around, but I'm not too sure about that. But if we're looking the earliest time period humans can possibly survive in then it maybe be that. Dinos are the next level to them, but I highly doubt medieval warriors could handle most dinos.