Hello Dee, you can definitely ignore the birth place list that comes up when you enter places and enter it as you think it should be.
I often use Wikipedia articles or other sources to get a bit of an idea, what places were named, when.
The article for Melbourne, indicates it was named Melbourne on 10 April 1837 but you are right would have still been in the Port Philip District which would have still been in the Colony of New South Wales.
If you have anyone earlier than that, it looks like it was briefly named Batmania, and before that Dootigala still under the Colony of New South Wales.