The point to realise is that species come into being via a series of infinitesimally small changes. There is never a specific point at which you can say that a creature came into being.
To give you some idea of how slowly bird species change, have a look at this bird. Then look at this bird.. See the difference? No, well neither does anybody who isn’t a fairly keen birdo. FTR, the second bird is your Nashville Warbler. The first bird is a closely related species.
Those two birds have been considered good species, so we can assume they have been isolated for a long time, though how long isn’t clear. Based on their current range, we could assume they were a single population at the end of the last glaciation event, ~10, 000 years ago. That tiny degree of change is fairly typical of the type of variation you can expect in birds in anything less than about a million years.
That essentially answers your question. It usually takes millions of years to produce really distinctive species. The middle ages were only a few hundred years ago, the birds would have been identical to what you see today. At the time of the last Ice Age your Nashville Warbler would have presumably looked
somewhat like a hybrid between the two birds in the photographs, which is hardly a distinctive difference from how it looks today.
As for when your warbler came into being, there’s no definitive answer. If you take a look at this bird, you might think it look similar, but it’s actually a distinct genus, and has presumably been separated from your warbler for at least 2 million years. So if you went back to the time when the very first humans existed, your warbler would like somewhere between that bird and your warbler.. Not really a huge difference and you could certainly be forgiven for assuming that it was the same bird.
If you went back ~10 million years you might expect your bird to look like this, which is a member of the same family.
You would really have to go back 20 million years or so to get to the stage where the bird is really distinctively difference. At that stage you start getting to the common ancestor of the warblers, cardinals and sparrows. If you can imagine a hybrid between a cardinal and a warbler, it’s going to be significantly different from your bird.
So from a layman’s POV, you have to go back somewhere between 10 and 30 million years before you start getting birds that are *obviously *not the same animal.