Food production the main reason is why New Guinea never got off the ground.
Papuans initially colonized the island and remain in the Highland areas (40,000BC or so). Austronesians came later on and did not expand into the higher altitude areas, remaining in lower altitudes and along the coasts (1600 BC or so). Dogs introduced by the Austronesians helped with hunting of native animals but also caused several species to go extinct.
Lack of food crops until the introduction of them in the last five hundred years plus lack of domesticated animals limited the growth of population. The peoples of New Guinea mainly raised non-cereal foods such as taro, yams, bananas, and sweet potatoes. Some of these plants would not grow in certain regions of the island. For example, yams were mainly a Highland crop, they also grew faster than taro which did well in other areas. Without across the board fertile soil, the soil would not support larger populations like other geographical areas like the Nile Valley, Fertile Crescent, China or Japan. Plus with the mountainous terrain, the high rainfall (annual 79 to 197 inches in the Highlands) and clearing forest for crops, resulted in erosion and loss of fertile soils. Look how quickly cleared regions of the Amazon lose fertility, thus having farmers there move on and clear more forest land. The same thing happens in New Guinea.
Note that malaria was found more so in the lower altitude regions of New Guinea, not the higher altitude regions. Thus there was more of a stable population at higher altitudes where it was malaria free.
There was not a unified political state either, most natives there had the family or multi-family unit. No one was actually in charge, people raised their own crops, what they could. Lack of a stable food source meant the lack of the progression from into a more centralized form of government.
Until the introduction of better food crops and food production methods, New Guinea could not support a population of 150 million inhabitants. It just reached 8 million inhabitants in 2016. Cannibalism (protein source and ritual feasting of family members) still happened, last recorded case was in 2012.
Last thing, there are over 1,100 dialects spoken on the island by the different indigenous peoples. Maybe a unified state would have one main language and several lesser ones, New Guinea never unified and remained a very diverse and divided island.
Across the board fertile soil, you say? Here's a map of the world by soil types:
And here's a map of South-East Asia by the soil concentration of organic carbon (the most important measure of how fertile soils are):
Now, look at New Guinea on that map. What sort of soils does it have? Which regions' soil composition does it bear the closest resemblance to? And how carbon rich are its soils, relative to all of the other islands? New Guinea arguably has the most fertile soil of any of the islands in the Indonesian archipelago- or, indeed, the world. And yes, the clearing of forests will result in erosion, which can and will result in the loss of fertile soils. But this can be solved by utilizing nitrogen-fixing crops, crop rotation and/or silviculture, such as that practiced in some isolated highland regions of New Guinea with
Casuarina oligodon, which has been planted by highland gardeners who've practiced an intensive traditional permaculture for over 3,000 years; using the wood of this tree for building-timber, furniture, tools and firewood, as well as tapping its edible resin as a supplementary food source. The tree's root nodules are known to fix nitrogen, and it is traditionally prized for its ability to increase the soil's fertility, with its abundant leaf-fall high in nitrogen and traditionally prized for mulch. If you're managing and maintaining the forest, as opposed to simply clearing it all away, you're not going to get that erosion, and you won't lose that soil fertility- which is why the region of New Guinea where this silviculture utilizing
Casuarina oligodon has historically been practiced (that maroon patch in the mountains of Irian Jaya, on the Indonesian side of the island) has more fertile soils than anywhere in Asia.
As for the state of New Guinean native civilization; it's essentially no different to that of the Japanese during the same stage in its development, in the few hundred years following the transition from the paleolithic era to the Iron Age. Headhunting and cannibalism were rife there too. Yes, there wasn't a unified political state. But was this due to the lack of a stable food source? Given that New Guinea was one of the agricultural cradles of civilization, and that many of the food staples which were first cultivated in New Guinea and disseminated to much of the rest of the world from there- such as taro, sweet potatoes, bananas, breadfruit, yams and sugar-cane- went on to become the dominant agricultural package of many cultures across the world, I'd very much doubt that. There really weren't any intrinsic barriers which prevented the progression from a patchwork of scattered, isolated tribal communities into a larger state, with a more centralized form of government, on New Guinea. Sure, it never happened IOTL. But this is AH.com, and this is an AHC; just because somewhere didn't develop in a certain way IOTL doesn't mean that a POD couldn't have changed that.