Melbourne is on the coast so an offshore platform will work on that endpoint. New Mexico has a spaceport already. Baring one opening up near Denver, flying to the west coast and then taking a Starship would be possible.
I'll take your word for it with respect to Melbourne, which is a lovely city I thoroughly enjoyed several decades ago. "Spaceport America" is a silly boondoggle that will never launch an orbital flight and will eventually be absorbed into White Sands missile range. Getting from anywhere in Colorado to any populated location not in Colorado takes longer than an hour. b^)