Tried asking this question on r/taiwan without much response, but somebody over there suggested I ask it here.
Linguistic oddities
There is a proto-Malayo-Polynesian term for "coconut" (*niuR) but no proto-Austronesian term can be reconstructed.
The word for "coconut" in Taiwanese Aboriginal languages is highly variable, and none of them that I am aware of bear any resemblance to *niuR. Examples are Siraya (Sinkan dialect) rudo, Pangcah (Amis) *'afinong,*^(1) Puyuma dudu’^(2), Sakizaya (closely related to Pangcah) abinung^(3), and Kavalan nuzu (which may be a loan from a Malayo-Polynesian language, explaining its slight resemblance to *niuR)^(4).
Some are straight-up loans (Paiwan & Rukai yasi)^(1).
This suggests that (cultivated) coconuts only became available to the Austronesians some time after leaving Taiwan.
Folklore
I have been able to find this account of an Amis folk tale about the origin of the coconut. However, per my understanding, presence of folklore about X is not evidence of ancient knowledge of X - folklore can also have modern origins.
There is also a story of dubious origin being circulated online in Mandarin (Simplified), not attributed to any specific Taiwanese Aboriginal peoples (the ambiguous term 高山族 (Gaoshan Zu, "highlanders") is used). It is about a girl who turns into a peacock (a bird which is not and has never been found in the wild in Taiwan) which turns into a coconut tree. I suspect that story is a figment of the imagination of somebody hailing from Mainland China.
My impression of the late date of coconuts' establishment in Taiwan
A Redditor who is highly knowledgeable about Taiwanese Aboriginal cultures has informed me:
There are many old Han paintings of the Siraya and adjacent tribes climbing up coconut palms & betel nut palms to collect fruit. For the Amis coconuts were used frequently as a food source, & both tribes nowadays still cultivate coconuts. Despite this, there aren't really any records or stories (that I know of) speaking of the coconut prior to the arrival of the Han.
And per Animals and Plants for the Formosan Natives, coconuts were "not introduced to Taiwan until a few hundred years ago".
Over in r/taiwan, I have been informed that (seemingly contradicting the above Redditor):
It seems that coconuts were introduced by Japanese during the Japanese ruling period to realize their fantasy of tropical, exotic landscapes. The very first coconut tree was introduced in 1888, but the tree did not survive. Later in 1901, they introduced another batch of seeds from Hawaii and successed this time. These very first trees are now in Taipei Botanical Garden, so maybe they have more detailed information about this topic.
Source (Traditional Chinese, pdf)
So, these sources are slightly contradictory - can anyone point me to more sources? I find it rather hard to believe that coconuts have only been established in any part of Taiwan since the early 20th century. However, it's almost certain that coconuts were only established in Taiwan way after the Austronesian expansion - some time after it was colonised.
What took coconuts so long to reach and get established in Taiwan? Per the below diagram, it seems that the Kuroshio ought to bring coconuts from the Philippines to Taiwan's shores. The climate in lots of Taiwan is clearly suitable for the growth of coconut palms.
Source: https://www.jstor.org/stable/2387846
I was speculating something similar to what happened in the Andaman Islands and northern Australia may have happened - i.e. that the indigenous people traditionally ate coconuts that drifted ashore, instead of planting them. However, in contrast with indigenous Andaman Islanders and Australian Aboriginals, all (?) Taiwanese Aboriginal peoples practised agriculture. Also, even if they traditionally ate coconuts which drifted ashore, it still doesn't really account for the lack of a reconstructible PAn word for "coconut".
^(1) Huwalu_ka_Using here
^(2) https://core.ac.uk/download/pdf/156640707.pdf
^(3) Formosan/Taiwanese Aboriginal languages (Austronesian)
^(4) Proto-Austronesian Phonology with Glossary and Proto-Austronesian Phonology with Glossary. They’re different books.
This is actually a pretty interesting question, and one that we may never know the answer to (due to reasons listed below). I think there are a couple of things to consider that might help us here: 1) coconuts (and palm trees) like to be in humid and warm climates (I'm no botanist, but this seems to be the case based on some quick Googling... please correct me someone if I'm wrong), and 2) most of the coastal Austronesian languages in Taiwan have died out.
So, better preserved languages like Bunun or Atayal (which are traditionally spoken by people who lived high in the mountains... which get quite cold and aren't covered in palm trees) not having a word for "coconut" is not very shocking. You mentioned the Siraya and adjacent tribes being depicted as harvesting coconuts, but we don't have much linguistic data on them, so they very well could have had a word for it (perhaps even something related to PMP *niuR) -- we will never know. Other, now-extinct languages once spoken along the western/northern coast like Taokas or Basay may have had words for this too, but if they did, it was likely never recorded.
That being said, you listed forms for Siraya, Puyuma, and Kavalan - all of which live on or close to the coast - and they look kind of similar to one another, but I'm not sure we can be very conclusive there (the Kavalan and Puyuma forms certainly have irregular correspondences, and coronals like r and d are a bit messy in the poorly-preserved Siraya data). The Amis/Sakizaya forms look a little like the Taiwanese Southern Min pin-nn̂g 'betel nut' (same family of plants), so I'm not sure that those are truly native, but at the very least they likely predate the Japanese yashi seen in Bunun/Paiwan. So as expected, at least people on the coast had them at an earlier date.
But why does PMP have a reconstructable word for 'coconut' and not PAN? Well, the lack of a reconstructable word for "coconut" in PAn isn't really an issue, because unless we assume their homeland was somewhere coastal, Proto-Austronesians probably wouldn't have had them. Based on linguistic diversity (and our current understanding of which languages were the first to branch off from the rest of PAn based on morphological developments^1 - Rukai, Tsou, Puyuma), it's more likely that PAn was spoken somewhere in the south(ish) mountains, not along the coast. PMP on the other hand has a lot more reliably reconstrucatble, ocean-adjacent vocabulary ('coconut' being one such example), which is expected of people who must have lived on the coast long enough to develop seafaring technology - I mean, the first place PMP speakers colonized was northern Luzon, which they needed to cross the sea to get to.^2
Could coconuts have been introduced to Taiwan very recently? -- it's theoretically possible, but many items introduced since the beginning of colonization by Europeans (in the 17th century) are pretty easily identifiable as loans (for example, many Formosan languages have tamaku or similar for 'tobacco'). The fact that the forms for Puyuma, Siraya, and Kavalan don't seem borrowed (at least at a glance) may indicate that they've had them for a while, but linguistically, that's about as far as it goes.
^1 Ross, Malcolm. 2009. "Proto Austronesian verbal morphology: A reappraisal." Austronesian historical linguistics and culture history: A festschrift for Robert Blust. Asia-Pacific Linguistics, College of Asia and the Pacific, The Australian National University.
^2 Blust, Robert. 2019. "The Austronesian homeland and dispersal." Annual Review of Linguistics 5: 417-434.
