I know there was sporadic contact between the northern coasts of Australia and Indonesia, perhaps there could have been more regular trade and an exchange of ideas that would have brought along a domesticate package?
There could have also been established contact with the Polynesians to the east, maybe the Maori in particular, perhaps something similar could have been established?
I'm wondering- WI the Makassan contact with the Northern Australians had been more productive, and/or had occurred earlier? IOTL, the contact between the peoples of the Indonesian archipelago and those of coastal North Australia revolved around the trade in
trepang, sea cucumbers. After making contact in the mid-1600s, The Makassans negotiated for the right to fish certain waters, as well as trading cloth, tobacco, metal axes and knives, as well as even rice and gin in some isolated cases. The Yolgnu of Arnhem Land also traded turtle-shell, pearls and cypress pine, and some were employed as trepang fishers.
This on its own could well be enough to establish a basic domesticate package and get a relatively advanced civilisation going- indeed, if the tales of the
Baijini people, mentioned in the Djanggawul epic of the aboriginal Yolngu people of Arnhem Land, have a factual basis, then it may well have already happened IOTL. And if not, then there are other ways to bring about the rise of a Northern Australian Baijini-style advanced civilisation. For instance, getting established trade links between Northern Australia and the rest of the Old World, via the Spice Routes, would IMHO be extremely easy to do.
The Aborigines of this area technically already had their own crop package IOTL- their founder crop was
Curcuma australasica, also known as Native Turmeric or the Cape York Lily. Named 'kumbigi' by the Aboriginal people of the Cape York Peninsula, they used to cultivate this plant, roasting and eating its roots. This close relative of Turmeric is present in the Cape York Peninsula, but it's common and widespread throughout Queensland. All it takes is a single trade vessel, either from or on its way to the Spice Islands, to find its way to these shores (such as the vessel from the Kilwa Sultanate which
appears to have make landfall here in the 11th century IOTL), and for the merchants to trade with the native Aborigines for their potentially lucrative
kumbigi spice. This variety of Australian turmeric has higher yields (in all aspects- size, weight, calorific value and curcumin yield) than the contemporary, traditional Indian varieties, and should accordingly be more valuable. This could easily provide enough incentive to add this region as another stop on the Spice Route long before the arrival of the Europeans.
Additionally, the Aboriginal people of the Cape York Peninsula aren't just limited to the single founder crop which they utilised historically IOTL. There are also four separate wild rice species which grow in abundance in the wetlands of Far North Queensland, which have only been discovered and identified by science in the past couple of years. They've now established that the Australian wild rice species are actually closely related enough to the domesticated Asian rice species to be interbred with them, combining the best elements of both the Asian cultivated varieties' higher yields and the Australian wild varieties' far greater resistance to diseases. IMHO, you don't even need an evolutionary POD for this to be perfectly plausible- it can be easily envisioned that such a civilization could indeed arise in this region of its own accord. Indeed, it's something of a surprise that it didn't IOTL.