As a point of comparison, there are a lot of stories about how Paul Bunyan created various lakes, mountains, and valleys. These are clearly invented backstories for part of the existing landscape.
I can't find a retelling of the Budj Bim story - are there elements of the story that are qualitatively different from stories about Paul Bunyan?
Or is it more that the local population has been in place for 40k years so these stories could be that old?