This seems like a counter-intuitive idea if you don't know about continental drift. I would assume to find totally different-looking animals across such an expanse of ocean.
Also, what did naturalists think when they found Australia and it didn't house similar species of large fauna?
Continental drift is not why the species that they found in the Americas were also in Europe. Continental drift explains fossils, the Bering Land Bridge, in the most part, explains why bears and wolves and other similar animals live on both continents.
The problem of animal life on a secluded island or "island" was not new in the Renaissance. Already in City of God (c.410 CE), Augustine asks how animals could possibly get to remote islands, since the Bible seems to suggest that all extant creatures are descended from the pair loaded into the Ark by Noah. He rejects the possibility of swimming, because some islands are too far away; and that people brought them along in boats, because that would require way too much skill and dedication to hunting and trapping dangerous beasts. He offers two possible supernatural explanations: angelic intervention on one hand, or the possibility that God brought forth new animals out of the Earth on islands. (The pairs rescued in the Ark, thus, are meant to prefigure the various peoples in the Church, rather than being the ancestors of all currently living animals. Augustine goes on to be very clear that all people are descended from one of Noah's sons, though, still).
Eleven hundred years later, the earliest explorers weren't concerned by either the similarities or the differences in the animal population. It actually took Europeans a couple decades to realize they were dealing with an unheard-of landmass (or landmasses). Obviously this is most famous in Columbus' contention that the islands he kept discovering must certainly have been among the "fifty thousand" islands of the Indies recounted in the (faux) travel narrative of John Mandeville. But even when he sailed the Central American coastline on a later trip, he did not think he had discovered a true "new world" but rather an otro mundo: the terrestrial paradise, a Garden of Eden wonder of Christian mythology. You can see in the letters of Amerigo Vespucci and Peter Martyr, as well, an evolution from following Columbus' belief that the landmasses were the coastline of Asia to accepting the facts of a "new world." It took some time.
For the most part, sixteenth century Europeans writing about the Americas tended to use the Old World to make sense of the new. The Amazon River gets its name from the product of European men's fervent belief that the fabled island of women must certainly exist somewhere in the New World. I've talked previously about how writers like Francis Moore used Old World equivalents to explain the new, describing American alligators to a European audience used to the medieval and Renaissance bestiary tradition as the crocodiles known/said to swim in the Nile.
This tendency to understand the New World's creatures with reference to the Old would prove a point of contention for 18th century naturalists like George-Louis Leclerc, the Comte de Buffon, who argued fervently that the llama is not the "camel of the Americas," but a llama, and we must understand it as a llama rather than a camel. (Buffon gets a justifiably bad rap in American pop history because of his belief in "American degeneracy," that is, that the climate of the Americas caused all animals and peoples native to the Americas to be weaker and lesser than those of the Eastern Hemisphere. On the other hand, from a scientific perspective, he recognized that "species" are to some extent an artificial distinction and that change over time can happen, so he's sometimes considered "halfway to Darwin.")
But rewinding a bit, the question of the origins of New World life seems to have been raised for the first time in print in a 1517 play attributed to John Rastell. Here it is not animals but the origin of the people that is in contention. The poet/speaker defers: "But how the people first began / in that country, or whence they came / for the clergy, it is a question."
Early responses in print followed the earliest explorers' accounts, claiming the New World was really the discovery of an Old World myth, from Carthage to the lost Hebrew tribes to a secret ancient Spanish empire. In 1580, Joseph de Acosta's Historia natural y moral de las Indias took up three competing explanations for the origins of human and animal life in the Americas:
Yup, the idea of a land bridge goes back that far! That quickly became the preferred explanation. Our good friend Buffon, mentioned above, accepted it as the most likely hypothesis. He thought that the animals of the Americas had walked there "of their own accord" when pushed out of the way of human civilization.
I'm afraid I can't speak to your question about Australia, though.
Are we talking Norse or Spanish settlers?