If you're taking a red-eye from Perth to Melbourne, you could get in two rounds at Cape Wickham Saturday afternoon and Sunday morning. Same for Barnbougle.
In Perth, Joondalup and Kennedy Bay are both public / resort courses, I believe; I've not seen the latter but it is highly regarded by Darius Oliver. The Cut, further south of the city, is another possibility I haven't seen.
Or you could fly to Melbourne, drive down to the Mornington Peninsula [1.5 hours], and play St. Andrews Beach and The Dunes, which are both generally considered better than the Perth courses.
None of the Sandbelt courses are public, all would be busy with member play on the weekend.