Perhaps named after an individual? For James Cook, Cookland if you want something simple or Jacobia if you want something posh. For Arthur Philip you could have Philippa.
Alternatively the monarch or their spouse were often used (Virginia, Carolina, Alberta, Victoria). George III was on the throne when we got involved with Australia, and Georgia is already taken, but you could use Charlotina.