I have to wonder why the Australians would come up with a fictitious creature that wants to eat them, when there are so many real life ones that do.
When humans first arrived there, there were all kinds of species of giant bird and megalania (basically giant Komodo Dragons or monitor lizards), so I reckon it's possible that ancestral memories of one of these apex predators led to legends of the Bunyip.
They had something similar to an elephant bird, and the cassowary is pretty damn scary too.