It is difficult to pin-point the exact source because there don't seem to be any etymological dictionaries of Malay just yet.
This is purely speculative, but the word for 'Dutch' in Portuguese is 'holanda', whose pronunciation is nearly the same as 'Belanda'. The Malays could've borrowed the word from the Portuguese during the struggle between Malacca, the Portuguese and the Dutch in the mid-17th century.
Another speculation is that the proboscis monkey could've been likened to the Dutch who conquered Malacca (perhaps their hair colour, their pot bellies and their big noses). The proboscis monkey is found in Borneo, which makes it unlikely that the Malays in Malacca came up with the term. Maybe the term was coined when there was interaction between the Dutch and the people of Borneo.
One last speculation is that, since the turkey is not a species native to the region, 'ayam Belanda' could've just been brought to Malacca by the Dutch, hence [ayam belanda = Dutch chicken/chicken of the Dutch].