Short answer: Yes, absolutely. Many names, from many different sources.

"Colonize" is a difficult term to work around. Are we talking about European colonizers? Or are we talking about earlier foreign populations, Indians, Arabs, Chinese, and others, who left their footprints centuries earlier? What about Europeans who visited these islands and gave them names but didn't actually colonize them? Or contemporary Indonesians who renamed other Indonesian islands?

It's easier to talk about each island on its own. I'll go through the islands in the order that you mentioned them.

• Borneo is derived from "Brunei," which we recognize today as the sultanate in northern Borneo. That name in turn is possibly derived from váruna, a Sanskrit word meaning "water" or "rain."
  In Indonesian, this island is called Kalimantan. This name comes from the Sanskrit kalamanthana, which means "burning weather island," likely referring to the island's hot climate.
  Other historical names include the Chinese name, Bo-ni, another derivation from "Brunei," and the medieval name Nusa Tanjungnagara, meaning "Land of the Tanjungnagara Kingdom"*—*a kingdom that, as you may have guessed, dominated the island at that time (early 1300s).
• Java doesn't have a very clear etymology. There have been a lot of ideas from a lot of scholars, most of them drawing from the names of local vegetation or from Sanskrit terms. As early as the 5th century, Chinese traders were calling the island She-po. In the 14th century, John of Marignolli called it Saba. These days, Indonesians call it Jawa.
• New Guinea is by far the most overtly "European" of the names on this list. In 1545, the Spanish explorer Yñigo Ortiz de Retez gave the island that name because he thought that its inhabitants looked like those of the Guinea region of West Africa. When the Dutch colonized the island two centuries later, they kept Retez's name.
  The other common name for the island is Papua, whose etymology is once again unclear. It may come from the phrase papo ua, meaning "not united" in the Pupuan language Tidore. Another theory is that it comes from the Malay phrase pua pua, meaning "frizzy-haired." Whatever the origin, "Papua" has become the main non-European term for the island, and Papua New Guinea, the name of the country on the island's eastern half, reflects the widespread usage of both names.
  In Indonesia, however, the island was long known as Iriyan Jaya, a term from the language of nearby Biak Island meaning rising spirit. This name was the official Indonesian name for the island from 1945 until 2001, when it was changed to "Papua."
• Sulawesi may come from the Bugis words sula ("island") and besi ("iron"), referring to the island's rich iron deposits, but this has not been definitively established. The Portuguese named the island Celebes when they arrived in the region, which may be a rendering or corruption of "Sulawesi." Its current name didn't come into widespread usage outside of Indonesia until after Indonesian independence in 1945, and "Celebes" is still commonly used today.
• Sumatra (also spelled Sumatera) has been known by many names. During the Indianization of the region in 7th–8th centuries CE, it was called Swarnadwīpa and Swarnabhūmi, Sanskrit terms meaning "land of gold."
  Exactly how these names became "Sumatra" is unknown. The current name is first mentioned in 1017 in a message to the Chinese Song Dynasty sent from the king of the Srivijaya Empire, who calls himself Haji Sumatrabhumi, or "King of Sumatra."
  This term didn't entirely take, as many names continued to be used well into the 19th century. Arabs referred to the island as Lamri, after the name of a small kingdom on the northern end of the island. Marco Polo calls the island Samara. Odoric of Pordennone calls it Sumoltra. Other visitors used other names. How exactly, and when exactly, Europeans decided to stick with the name "Sumatra" is unclear.

In conclusion: Yes, all of these islands have had many names. Some of them we know, some of them we don't know, and some of them we know but we don't know where they came from. Most of them are a hodgepodge of different languages and terms, chosen by a whole host of explorers, empires, and populations. That's part of the reason why etymology is so cool! It can tell us so much about the history of a name, place, or thing, if you manage to find enough clues to coax it out.

Here is my hodgepodge of sources and further reading:

Eugene Linden (17 March 2011). The Ragged Edge of the World: Encounters at the Frontier Where Modernity, Wildlands and Indigenous Peoples Meet. Penguin Publishing Group.

Siti Norkhalbi Haji Wahsalfelah (2005). "Traditional Woven Textiles: Tradition and Identity Construction in the 'New State' of Brunei Darussalam." Universiti Brunei Darussalam.

Suyatno. "Naskah Nagarakretagama" (in Indonesian). National Library of Indonesia.

Raffles, Thomas E.: History of Java. Oxford University Press, 1965.

Lombard, Denys (1990). The Javanese Crossroads: Essay of global history.

Yule, Sir Henry (1913). Cathay and the way thither: being a collection of medieval notices of China vol. III. London: The Hakluyt Society.

Bilveer Singh (2008). Papua: geopolitics and the quest for nationhood. Transaction Publishers. p. 26.

Ploeg, Anton (2002). "'De Papoea' What's in a name?". Asia Pacific Journal of Anthropology. 3*.* (1): 75–101.

Watuseke, F. S. 1974. On the name Celebes. Sixth International Conference on Asian History, International Association of Historians of Asia, Yogyakarta, 26–30 August.

Everett-Heath, John (2018). The concise dictionary of world place-names (Fourth ed.). [Oxford]: Oxford University Press. p. 1131.