I'm German and my husband USC and we ended up getting married in Denmark.
I met with a very friendly lady from the Standesamt of the city where we used to live and she told me the following:
My husband would have needed:
- birth certificate with notarized translation
- proof of income (no translation necessary because he worked in Germany at the time)
- certificate of freedom to marry from the consulate (notarized translation)
the Standesamt would have sent all this to the "Oberlandesgericht" (Higher Regional Court) to check all the papers, the lady said this could take anything from 4 to 12 weeks and would have cost a certain percentage of his monthly income- she wasn't sure how much exactly (something like 7%).
Only after the approval of the Oberlandesgericht is when you can actually set a date with the Standesamt.
Keep in mind- this is only one experience from one Standesamt in Germany, I don't know if it's the same everywhere.
Long story short- we decided to get married in Denmark.
All that was needed for Denmark were copies of our passports (his showing his Visa for Germany) and a confirmation of residency (Meldebestätigung) from the city we lived in.
And a document from the Danish office with our biographical data and that we intend to marry, that we're not related

All that was sent to the Danish office together with 500DK (about 80€) and after 4 days I could call to make an appointment!
They were very helpful and friendly, spoke both German and English fluently.
It was a great experience!