You have a PhD. That's obviously "more" than a Masters and should count. The problem here (as Wrzlprmft also points out) is a cultural issue. The German administrators are familiar with the German system where one does a Bachelors, then a Masters, and then a PhD. So everyone with a PhD also has a (separate) Masters certificate. They're also sticklers for paperwork, so if the paperwork says a Masters is needed, you need the certificate that you've completed a Masters.
The complication arises as you've done your PhD at an institution which doesn't bother with the intermediate Masters designation(*), and goes directly from Bachelors to PhD. The bureaucrats are confused because the regulations say you need a Masters certificate, and they can't find anything in what you submitted that looks like a Masters certificate.
You're unlikely to convince them that they regulations can be ignored in this case, but what you likely can convince them of is that your PhD certificate also counts as a Masters certificate.
Because in reality, your PhD likely is the equivalent of both the Masters and the PhD. In the German system, a Masters is an ~2 year degree where the student takes a combination of classes and research, and writes and defends a thesis at the end. Then the PhD is a ~3-4 year degree where they just do research and write and defend a thesis at the end. (All this is roughly speaking -- different institutions and individuals have variations.)
I'm guessing(*) your PhD program was a ~5-6 year degree, with a combination of classes and research in the first ~2 years, and then research in the last ~3-4 years, followed by writing and defending a thesis at the end. There was likely also an event (possibly colloquially known as "prelims" or "quals") at about the 2 year mark where you had to write up a document and then defend it. -- Or in other words, it was a single program which combines the features of both the German Masters and the German PhD programs. Additionally (though institutionally dependent), it's also likely that - had you decided that the PhD program wasn't your cup of tea - at about the 2 year mark you would have been able to write up a thesis, defend it, and then leave the program with an official Masters degree (which is further recognition that the first two years of your program is a Masters equivalent).
So what's likely helpful is to convince the bureaucrats that your Australian PhD certificate counts as both a PhD and a Masters. I'm not sure what documentation you'd need to do this, but that's the angle I'd recommend to take when asking about it: "I'm terribly sorry about the confusing and backward way Australia runs its graduate education program. It says PhD, but it's really equivalent to a combined Masters/PhD program. What documentation do we need to prove that?" -- It may seem like a minor phrasing change, but going from "I don't need a Masters, I have a PhD!" to "My PhD certificate should also meet the requirements for a foreign Masters equivalent." is an important one for regulation-following sticklers. The first one asks them to bend the rules and special case you, but the second accepts the regulations and tries to satisfy them.
(*) I'm assuming. I'm not overly familiar with the academic system in Australia, and am basing it on the system in the United States.