メルボルンとエアーズロックなら…

あまり詳しくはないのですが…どなたも書き込まれていないようなので、僭越ながら。

メルボルンとエアーズロックの2箇所だけを見たいということでいいんでしょうか?
それでしたら普通に日本⇔メルボルンの往復便を取って、メルボルン⇔エアーズロック間も飛行機を使われるのが無難なのではないでしょうか。
期間が短めですのでバスや鉄道での移動は難しそうです。

もちろん他の地域も見たいということであればケアンズ→エアーズロック→メルボルンのような回り方も可能だと思いますが、往復便ではなくなってしまうので予算的には少し高くなります。
このへんについてはkayo-pさんの予算と、どんな旅行をしたいか、という希望次第だと思いますので私のほうからはこのルートがいい!というようなお勧めはできません。
あまりお役にたてなくて申し訳ないのですが…ご参考になれば幸いです。