Pre-euro Australia was more like Europe with different tribes/nations that shared common characteristics yet still had their own languages and cultures.
Compare and contrast the difference in sophistication between the Romans and the gauls or germanic tribes around 200AD, they would seem totally different worlds. It could have been similar in Aus.
Other indigenous Australian groups invented the boomerang - first ever practical use of aerofoil technology - precursor of modern flight and the woomera which launches a spear around 700-800m with accuracy.
From what I remember their art was somewhat codified so it could almost be "read", this would make it easier to share information across time and place.
If you have groups on two ends of the continent sharing very similar stories, then at least you'd have to allow the reasonable possibility it's more than just random noise.