The combination of high, rugged mountains and impenetrable jungle make New Guinea one of the most difficult places in the world to unite in any way at any point in history. My first instinct here would be to have the entire island come under the dominion of a colonized that for some reason becomes quite serious about importing colonists, and have them spread across all the coasts, using modern high-intensity agriculture and medicine to sustain a population so high that it's at least 3 times larger than the population of natives. They could, for example, clearcut and settle on the large plain on the southern portion of the island.