New Zealand is easy, since Polynesians only reached it around a thousand years ago. You could easily have them set off later and just be unable to reach it before Europeans show up, or never discover it for one reason or another, and so there's no human colonization to destroy the megafauna until Europeans arrive. Some of the island's megafauna will probably go extinct anyway, but part will probably survive.
The Americas are much more difficult. The problem is that there was evidently a pump from Siberia to the Arctic region of the continents, as shown by the multiple migrations that have taken place along that route. It's hard to see how you could avoid or delay that altogether without invoking bats, and you probably need that to save a significantly larger part of the American megafauna until modern times than existed IOTL.
Europe and Australia are basically impossible. Humans have existed there for tens of thousands of years, so any megafauna there would have to be post-human megafauna, like in Africa. That basically calls for greatly slowing down human technological and social development so that new megafaunal species can evolve that are better adapted to the presence of humans than their original inventories, but that still doesn't really answer your question. Aside from something that prevents humans from emerging altogether, even early humans, I don't think you can preserve European or Australian megafauna.
I think of all the semi-large to large landmasses, it would be least ASB to have the Malagasy megafauna (such as the elephant birds) survive as I believe Madagascar was the last "large" island to have a permanent human settlement.
Madagascar was definitely settled a long while before New Zealand, though.