The story
The first Europeans to encounter their skins were the voyagers in Ferdinand Magellan's circumnavigation of the Earth. Antonio Pigafetta wrote that "The people told us that those birds came from the terrestrial paradise, and they call them bolon diuata, that is to say, 'birds of God"." "Bolon diuata" appears to be closer to Malay burung (“a bird”) and dewata (“a god”).
Etymology from Wiktionary, CC BY-SA 4.0.