As soon as you talk to a notary to prove that you're really opening a company you can get the provisional business license, or whatever they call it, to open a bank account. After you open that bank account you need to talk to the notary again to start registering the real company. Then you need to transfer the bank account from the place holder company to the real company.

I may be misremembering the exact steps because I tried drilling all those memories out of my head as soon as I left Germany.