Even with the end of the Ming voyages you can still have merchant activities in the south seas. Actually I'm pretty sure there were. You could then have a non-state backed colony in the 15th century.
However such a POD would likely change Ming government policy toward SE Asia in due course, significantly altering Chinese history. Even if it does not, and this Chinese Australian colony develops in isolation, it would eventually attract so many immigrants (and absorb more modern Dutch technology) to make later British control unlikely.
The best bet would be a much later POD. Say around the early 18th century when considerable numbers of Chinese migrated to the Dutch East Indies. Batavia (Jakarta) alone had over 100,000. Some of them could have set up a settlement in Perth or some such area. In the 1730's there was a massacre of the Chinese known as Batavian Fury, in which the Dutch tried to seize the businessholdings of wealthy Chinese and deport the poor to Ceylon for slave labor. This incident caused the Indonesian Chinese to scatter throughout the East Indies. Had there been a small colony in Australia, certainly a large number would have sought sanctuary there.
By early 19th century the British could claim the continent along with the Chinese colonies and bring in British settlers.