The map below ( there are better ones ) gives some indication of the ancient situation in south china before chinese expansion ( roughly 4 th century BC and after).
If basically right, then : south west china had tibeto-Burmese languages. In the other southern parts , austro -asiatic languages and thai-kadai languages .
Fujian ( min yue area )is presented as a question mark . Its between between daic and austronesian regions. They could have been still austronesians ( who, for example had remained on the coast or had settled there ) or daic speakers or maybe included groups of both ( IMO the best option for the time).
If the ancestors of the taiwan natives came from south east china, then a linguistic relation with Daic and/or austro asiatic seems more promising than sino tibetan. Not that this automatically means that daic, evolved in austronesian languages or vice versa. A common proto language might have evolved in separate families, as sometimes suggested.
Maoris are ultimately related to the other austronesians but in particular to tahitians and Cook islanders. They sailed from there and settled NZ some 1000 years ago. Long open sea trip, some 3000 km.