Change in their core beliefs and values leading to large population growth.
(And they need to be world-leading boat builders too.)
The hundreds of Aboriginal "communities" (I was told "tribes" isn't PC) weren't all isolated. They had trade, connections, and shared identities with their neighbouring communities. These groupings among these peoples were into what was analogous to "nations". Some of their borders fit quite well with your segmentation.
Referring to a a handy overview of the aboriginal peoples names / identidies / "how should I refer to you" guide:
One would cover all of western Australia,
This is basically the Noongar peoples already.
One would take up the northern territories and what is known as Queensland in our world including northern parts of southern Australia and the island of Papua.
This is basically the merging of the Melanesians, Murrie and Anangu peoples.
The third kingdom would cover the rest of Australia and the islands in Oceania.
This is the merging of the Koorie, Nunga, Palawa and all the Torres strait islanders and the rest of Oceania. This is quite a conquest, and leads to what I think is the biggest hurdle for your story:
The sea links will need a 100,000 workers alone just to stay connected. Plus epic tech:
Your empire include a lot of disconnected islands: Fiji, Micronesia, Kiribati, Tonga, Vanuatu, Solomon islands, all of NZ, PNG, Tasmania, Timor, Norfolk Island, KI, Christmas Island, and so many more. 10,000 islands in Oceania alone. They all are going to require basically a ferry service such they remain in constant contact with the rest of their empire. That will require many people to maintain and operate the fleets of ships needed for this.
You'll probably also need improvements in manufacturing, science, and maths in order to build reliable ships that get out into Oceania with decent safety. I've done Australia to Vanuatu on a massive modern cruise ship and it was rough and unpleasant and took days. If your tiny wooden ships are smashed to pieces by big waves, the empire is disconnected.
These improvements to science, manufacturing, maths, chemistry, etc may tax the verbal-only communication and education methods of the aboriginal people. They may need to develop a complex written language too such that this knowledge can be taught forward. Unless you want to try to picture an elder telling the young adults "the Dreaming story of that snake that raised e to the power of i * pi".
So - how do we build kingdoms here?
To maintain a kingdom over these distances, you need good communication to exert control over it. The excellent shipping links need to be complimented by messengers travelling between settlements carrying stuff. You need to have allegiance sweared between cheifs and the king, you need to have taxes paid and transferred, goods transferred where they're needed, plus information like orders need to be transferred. You'll need communication networks between settlements and a hierarchy of lords / chieftains / etc all ultimate loyal to the king. This requires a lot of people to implement, especially pre-telegraph.
Roman-style roads would come in handy here, but the distances are so vast and the population so tiny its unfeasible.
The population density of Australia in this time period was low, estimates range from 318,000 to 1,000,000 over 8 million sqkm. This is very sparse. 1 person per 30sqkm. If each lord needs 2 guards, a messenger, a tax collector, and a personal servant, the settlement extends out to 180sqkm before it even includes subjects. Large towns will obviously get better scaling, but they'll be so far apart that communication will be hard.
The roman empire was about 70 million people in 4 million sqkm. Australia and all the islands you're including is about 10 million sqkm. You'll need to crank this population up by orders of magniude in order to make it possible to unify them under one kingdom. Cranking the number of people up will strip the land of food - you'll need agriculture to support such a large population.
Destroying the outback and replacing it with big farms are totally against the Australian Aboriginal cultural identity. So, to achieve what you want, you'll need to essentially replace their culture with one not focused on being close to the land.