I mean, these were intelligent people. Just as intelligent as, if not more intelligent than, the average person nowadays. How could someone see a wildebeest and believe this stuff?

This is an extremely problematic idea when approaching the marvelous or supernatural in history. It is entirely possible that individuals like Pliny were exceptionally intelligent but still believed in poisonous wildebeests; they possessed a very different culturally informed worldview than yourself where such seemingly absurd beliefs could comfortably exist alongside cultural constructions such as rationality or 'common sense'. Rationality is relative, and what seems rational to us today might seem absurd and childish to our descendants in the future: consider the cultural attitudes of many of our contemporaries who 'rationally' oppose things like recreational drug use or homosexual marriage. Will our own beliefs and convictions make sense or seem rational centuries from now, when our culture seems alien and our scientific knowledge looks primitive?

We have to view these strange beliefs within the wider intellectual and cultural contexts that these individuals existed in rather than viewing them as childish superstitions. For example, when we read that medieval people believed that marvelous races and beasts like your wildebeest lived in the margins of the world, we would try to "make sense" of that belief by researching how those people understood things like the shape of the globe, the nature of the marvelous or supernatural, the intellectual tradition of the marvelous in literature (from sources like Pliny) and how nature as a system worked. What we would discover is that medieval people (I'm generalizing here, don't hurt me) believed that the world was circular and that marvelous beings regularly appeared in the globe's savage periphery but only occasionally in its more perfect center (such as monstrous births). We would also discover that those people had very different definitions of the categories of natural and supernatural, and that the only supernatural forces were those of the divine; everything else, like men, goats, marvelous races or venomous wildebeest were natural. We would also find out that these people thought of nature as a system with fixed laws rather than general habits (as we do today) meaning that because nothing can exist beyond those fixed laws, anything seemingly marvelous or supernatural must be the product of some law, legitimizing its existence.

Now we can properly understand why people believed in such (by our own standards) absurd things. We just have to reconstruct the culturally inherited worldview that these beliefs existed in and find out in which way they were rational or common sense to their believers. This all means that pre-modern people weren't consciously superstitious or irrational when they believed in men with dog heads, witchcraft, vampires or flying snakes. They were instead thinking and acting rationally within the intellectual and cultural framework that they existed in and inherited just as we do today.