The easiest way to go about this would be by having as early a POD as possible, and by having the Europeans establish their own spheres of influence in Australia by proxy. The Makassan trepangers had been visiting N.W. Australia. for centuries before the European colonialists arrived; 'Marege' was the Makassan name for Arnhem Land (meaning literally "Wild Country"), from the Cobourg Peninsula to Groote Eylandt in the Gulf of Carpentaria, while 'Kayu Jawa' was their name for the Kimberley region of Western Australia. The Makassan crews established themselves at various semi-permanent locations on the coast, to boil and dry the trepang, before making the return voyages home, four months later, to sell their cargoes to Chinese merchants; negotiating with the Aborigines for the right to fish certain waters. The exchange also involved the trade of cloth, tobacco, metal axes and knives, rice and gin. The Yolgnu of Arnhem Land also traded turtle-shell, pearls and cypress pine, and some were employed as trepangers- rock art and bark paintings confirm that some Aboriginal workers willingly accompanied the Makassar back to their homeland of South Sulawesi, across the Arafura Sea. So, for the POD, how about having a few of those Makassan merchant pioneers establish permanent settlements at their colonial bases in the Marege and Kayu Jawa regions of Australia back in the early 1500s; starting to establish a varied collection of competing sultanates, principalities and kingdoms of their own, as well as significant inter-island and inter-continental trade, either just when or just before the first European traders begin to arrive?
If the situation in Australia (Northern and Western Australia, at the very least) is an extension of the situation in the East Indies, then the Europeans' colonial efforts on Australia could follow a similar path; with the East India Trading Companies competing to establish exclusive relationships with the most powerful sultanates, primarily through the use of soft power, possibly engaging in proxy wars backing their respective partners, and establishing their own defined spheres of influence that way? In such a TL, where the Makassans had established permanent trading settlements rather than transitory trade posts on the Australian mainland, both the Portuguese and the Dutch would've almost certainly got in on the act from the off, with the contest to colonize Australia effectively becoming the Southern theatre of their quests to dominate the source of the lucrative spice trade in the early 16th century, and to extend the missionary efforts of the Catholic and Protestant churches respectively. And of course, once either the Makassans or the Europeans start pushing inland from these northern outposts, discovering the world's highest concentration of diamonds in the Kimberley/Kayu Jawa, and some of the most productive goldfields yet uncovered (at that stage) in Arnhem Land/Marege, there's no way that you wouldn't have gotten a colonial rush to secure trade monopolies over these valuable new lands. Enter the Dutch, Portuguese, Spanish, British and French; and given how vast and relatively under-populated Australia is, it wouldn't be out of the question for all of the colonial players who decided to get involved in Australian colonies to maintain their grasps on Australian colonial territory to the very end, in a manner akin to the Portuguese clinging onto East Timor IOTL.