Maybe a Christianity-related route for Indonesian discovery and colonisation? Let's have the Himyarites of Yemen convert to Nestorian Christianity instead of Judaism, and Islam is butterflied. Over the next few centuries, Nestorians in India increase in number and power, and eventually a powerful Tamil state like the Chola dynasty converts to Christianity. By the early 2nd millennium AD, a powerful Javanese state like Majapahit converts to Christianity.
Indonesian Christianity ends up with a strong monastic tradition, and the vague concept of a desert land to the south appeals to monks seeking isolation. Soon, monasteries exist in the Kimberley and Top End, trading with Aboriginals (and converting some), along with attracting others from the motherland in time.
Is it possible that increased presence of the Majapahit and the Bugis on North Australia could result in the Portuguese discovering it during the 16th century?
The Portuguese probably did discover Australia in that time, but they thought nothing of it. It isn't too long before the Dutch discovered Australia, and Portugal was active in Timor which isn't too far away, so it's very plausible if not OTL.