I do believe that is your only option for Star Alliance, departing Sao Paolo.
Once in Jo-berg, you can get to Perth non stop, otherwise you will have to connect via Singapore on SQ metal to Perth, Adeleadie Etc...
There are no direct JNB-SYD/MEL flights from South Africa that are available for redemption.
South African Airways code shares with Quantas for this route.