You wouldn't stop at all of those places - but they could stop at 2. For example Paris on the way TO Perth, and Hong Kong on the way home FROM Perth (depending on allowable routings).

I would suggest booking them to Perth (easier to find flights in my experience) and then a separate ticket Perth-Melbourne-Perth (paid). There are very limited Star Alliance flights to Australia and no Star Alliance flights within Australia which is why you can't visit both cities, because you would have to connect outside of Australia and that goes way past mileage limits