I'll leave aside the question about historical place names not being found by Google Maps and whether the style described on http://www.wikitree.com/wiki/Location_Fields should change. We should discuss that separately.
Regarding categories inside birth and death location fields, I'm afraid the answer is no, the category tags have to go in the bio/text area of the page. What's entered in the location fields is just text. What's in the body of the page is "wikitext". Categories are a wiki function.
Regarding subcategories, those are created by categorizing a category. The same sort of tag you'd put on a profile can go on a category. For example, on http://www.wikitree.com/wiki/Category:South_Australia I put [[Category:Australia]].
Regarding Australia not appearing on http://www.wikitree.com/wiki/Category:Regions that's because http://www.wikitree.com/wiki/Category:Oceania does. That is, there's a further subcategorization. Maybe that's not right? I have no idea.
Regarding the links in the text, the reason [[Medindie]] didn't work is that it needs to be [[Category:Medindie, South Australia]], i.e. with "Category:" in the link. Otherwise it's like you're creating a general WikiTree Help or Genealogy Help page, and that is restricted currently restricted to Supervisors.
For reference: http://www.wikitree.com/wiki/Using_Categories
We might need to improve the explanations on that page.