It lives on in my heart and one of these days I will continue in some form somewhere
If anyone's qualified it'd be you, dude.
Coastal Queensland has the same cilmate and fishing the Polynesians were used to, and far more land than all of Polynesia combined. With agriculture and domesticated animals they would quickly outnumber local natives and intermarry, expand overland in time. As a maritime culture, this new Australia would not become isolated and instead participate in the Southeast Asian trade network.
I'm suspicious of the proposition that colonizing Australia circa 4000-2000BCE wouldn't work. The northern and more so the eastern coasts of the continent are hospitable (there are rain forests in New South Wales fer chrissakes) it isn't hard to adapt fishing to new areas, and the natives are divided into a thousand small cultures rather than being unified in any way. And conflict with alien cultures is just what you need to promote larger unified states among the Polynesians. Getting back and forth from Australia to Taiwan is also navigationally easier than hitting tiny islands in the middle of the Pacific, so maintaining ties to Taiwan is easier, allowing your iron age boost.
Climate is just one piece of the puzzle; the actual physical environment is another. Australia's lushness is only deceptively so -- those rainforests are old-growth that probably took a very long time to get that way. Australia is probably the least fertile continent on Earth; much of its soil's nutrients have been washed away, and any geologic or glacial processes that could replenish nutrients haven't happened in millions of years. Australia's British settlers learned this the hard way. Even today agriculture there is challenging with farmers in the Murray watershed and elsewhere having to deal with increasingly saline soils. Australia's wheat belt was originally sandy, nutrition-poor soil that is now artificially fertilized.
Consider this: Immediately to the north of Australia is New Guinea, which is vastly more fertile than Australia and requires less effort to farm. It is accessible via a chain of increasingly larger fertile islands from Tonga to Fiji westward. Even Fiji, right next to the heartland of Polynesia, rivals the total habitable territory of the Polynesian Pacific (if you take Hawaii and NZ out). Both of these islands are inhabited by Melanesians, a similar Austronesian group with their own maritime traditions (the Fijian drua was one of the largest catamarans in existence then). If people are of little consequence, why was Fiji not significantly re-colonized by Polynesians? Or Vanuatu, or the Solomon Islands at least if not New Guinea outright?
Moreover despite the large trade connections and seafaring capability of Melanesia, they did not even obtain any significant amounts of materials, technologies, domesticates or ideas from the nearby Indonesian kingdoms, far closer than Taiwan (and the kingdoms and sultanates were at least aware of the Papuans), and if any trade of this variety existed it did not drastically change Papua society. Granted one could say that the Polynesians' increased drive for exploration, slightly increased political complexity and a few more plants (like sweet potato) could make a bigger difference here but it all begs the question as to if they ever saw a need? How alluring do the trade goods have to be to encourage them? Would it even have the desired effect?
Polynesian colonization seems to have mainly focused on finding new, empty lands to cultivate and settle. Finding people already using that land might defeat the point in their eyes.