There was ongoing diplomatic and trade links between the Sultanate of Aceh (Indonesia) and the Ottoman Empire which provides the logical leap off oint for eventual Ottoman expansion into Australia.
The Ottoman-Aceh relationship kept the Portugese from dominating the Indian Ocean trade and only came to an end after the Aceh war when Dutch forces who had been fighting 'pirates' in Malakka turn their attention of Aceh over a perceived violation of treaties. Aceh claimed to be an Ottoman Protectorate but this was rejected by the European powers and the Ottomans were unable to aid due to problems in Yemen. Your POD can fit anywhere within the period, but probably depends on Ottomans having affairs under control at home.
The other issue is making Australia more attractive as a destination for more than sea cucumbers
http://en.wikipedia.org/wiki/Ottoman_expedition_to_Aceh
The 1564 embassy to Constantinople was sent by Sultan Hussain Ali Riayat Syah.[3] In his missive to the Ottoman Porte, the Sultan of Aceh referred to the Ottoman ruler as Khalifah (Caliph) of Islam.[3]
After the death of Suleiman the Magnificent in 1566, his son Selim II ordered that ships be sent to Aceh.[3] A number of soldiers, gunsmiths and engineers were sent in an Ottoman fleet, together with ample supplies of weapons and ammunition.[1] A first fleet was sent, consisting of 15 galleys equipped with artillery. It had to be diverted to fight an uprising in Yemen.[3][5] Only two ships eventually arrived in 1566–67, but numerous other fleets and shipments would follow.[1] The first expedition was led by Kurtoğlu Hızır Reis. The Acehnese paid for the shipments in pearls, diamonds and rubies.[6] In 1568, they (the Acehnese), besieged Malacca, although the Ottomans do not seem to have participated directly.[3] It seems however that the Ottomans were able to supply cannonneers for the campaign, but were unable to provide more due to the ongoing invasion of Cyprus and an uprising in Aden.[7]