So what about Mozambique then? What if Zheng He carries on down the coast of East Africa on his 4th Voyage? IOTL, he turned back after reaching Malindi (the southernmost trading outpost which wasn't part of the Kilwa Sultanate/ Confederation at the time); what if he'd kept going to Mombasa (only 120 miles further), thence on to the other major port cities in the Kilwa Sultanate which he'd hear about in Mombasa- Zanzibar, Kilwa and Mozambique, eventually travelling down the coast as far as Sofala, before turning back and making the return voyage (dropping by the small trading posts claimed by the Kilwa Sultanate along the western and northern coastlines of Madagascar along the way)?
Sofala, in particular, would be an obvious choice for Chinese colonisation. This crucial port city, which was at this time the greatest export centre of gold and ivory in the world, still technically belonged to the Kingdom of Monomutapa at this point; the Swahili community had to pay tribute to them for their permission to reside and trade there. The Sultan of Kilwa only had jurisdiction over the Swahili residents, and his governor was more akin to a consul than a ruler- Sofala still retained a great degree of autonomy, and discontent simmered in this city at the perceived interference in their affairs by the Sultan of Kilwa.
Sofala was easily the most dominant coastal city south of Kilwa itself. The mission objectives assigned to Zheng He's treasure fleets by the Yongle Emperor were to establish Chinese dominance and impose imperial control over the Indian Ocean trade; to impress foreign peoples in the Indian Ocean basin; to extend the empire's tributary system; and to bring back treasure. As such, Sofala is by far the single greatest prize on offer within Zheng He's reach, and its acquisition could go the furthest to meeting all of these objectives. The gold output of the Kingdom of Monomutapa (and its successor IOTL, the Rozwi Empire), all of which was traded through the port of Sofala alone, would exceed all of the gold brought back from the New World until the dawn of the nineteenth century. As such, after Ming dynasty causes hyper-inflation by issuing too much paper money, causing hyper-inflation and forcing them to suspend the use of paper currency in 1425, Ming China would adopt gold, since they'd now indirectly control the largest source of this precious metal in the entire world (with Monomutapa swiftly becoming either a Chinese vassal state, getting subjugated in a similar manner to the Kingdom of Kongo's subjugation by the Portuguese, or becoming a major world power in its own right, enriched and empowered by selling its gold to the Ming in exactly the same manner that Japan was enriched and empowered by selling its silver to the Ming IOTL), instead of silver as IOTL. As such, when the Europeans get around the Cape, their merchants won't have anywhere near the leverage or soft power that they did IOTL; and this one POD may be enough to butterfly away the second wave of European colonialism entirely.
And all Zheng He has to do is get there, and to outbid the Sultanate of Kilwa- which, given the cargo capacity of the treasure ships in his flotilla, should be a trifling matter- for the Kingdom of Monomutapa to oust the Sultanate of Kilwa's consul, and grant their permission to reside and trade in Sofala to the newly arrived, far wealthier Ming Chinese traders instead. And there'd be plenty of them. Just from the shipwrecks IOTL, you have the people of Pate Island on the Lamu archipelago who've been shown to have descended from 20 stranded Chinese sailors from Zheng He's fleet, founding the settlements of "Old Shanga", and "New Shanga" on the islands, and introducing Chinese Ming Dynasty tombs, made out of coral, to the graveyards on the island.
Several tribes even further south, to Cape Town's north, claim descent from Chinese sailors during the 13th century, a few decades prior to Zheng He's expeditions; visibly similar to the Chinese in their appearance, with a Mandarin-derived tonal language, they call themselves the Awatwa, or "abandoned people" today. ITTL, if these communities aren't abandoned by the rulers of China, but instead remain connected to China through the establishment of trade links in the same way that the Chinese communities in South-East Asia did, then these Chinese traders and settlers could easily form overseas communities which come to dominate large colonial enclaves, and perhaps even Sinicise large regions permanently. Madagascar, for instance- at this time, Madagascar's aboriginal population was less than a third that of Taiwan. So, even in spite of the greater distances involved, I'd say that it wouldn't be far-fetched at all for the island of Madagscar ITTL to become a Chinese colony in much the same manner as the island of Taiwan did...