Firstly, they dont share any common language.
Well, it's not like any of the individual countries do either, with the partial exception of Fiji. Standard English for government business and pidgin English for trade would be sufficient
linguae francae outside New Caledonia, and if New Caledonia had been under British or Australian colonial rule, they'd work there as well.
Secondly, if you include new guinea, that would so dominate the union as to make the islands powerless.
The PNG economy isn't
that much bigger than Fiji's and New Caledonia's combined, and PNG is much less developed than either of those countries. Suva or Noumea could give Port Moresby competition as the political center of the federation, and would probably have a considerable edge over Port Moresby as financial and educational centers (nobody, but nobody, would put their bank headquarters in Port Moresby if there were another choice).
The best way to do this would probably be for all the Melanesian islands to be ruled by one colonial power - as stated above, Britain or Australia would probably be the best candidates - and for that power to administer them as a single territory. I can't see a pan-Melanesian unity movement gaining traction if the islands start out as separate states - hell, unity even within a single island group is a pretty contentious concept across most of Melanesia - but if they start out as a unit, I could imagine them staying that way out of inertia, and eventually becoming integrated at least at the elite level. Institutions like the University of the South Pacific (Suva), a common currency, regional banks and a single law code would help at that level, although they might not have much practical effect in the villages.