First off, the Vertragsstrafe for you not showing up is entirely legal1, and unfortunately fairly common2. There is no reason to have this both ways. For a no-show with a two week notice period it seems you cannot have a higher penalty as half a month's worth of salary before tax (Bruttomonatsgehalt). It cannot be much higher3.
But we're talking about the other way around.
So the company told you they don't want you to start. They could make you come in on the first day, and then give you the boot. They could tell you to go straight back home (which is called a Freistellung in German) and the contract would then end after two weeks. They would have to pay you, but you were not allowed to have another gainful employment in these two weeks. You would have healthcare for that month and it would count towards your government pension (Rentenversicherung).
Or they could save you all the trouble and just ask you to not come in at all. I have seen this happen to people. It's the nicer thing to do really. Effectively you would both agree to declare the contract void, and it's as if it never happened.
You might insist on them doing the long route, but they'd have to still HR-onboard you, get all your details, do the tax stuff and so on. It's a lot of hassle and there is probably a good reason they decided not to hire you after all. Probably there is a business reason, like a project being cancelled, no funds to pay you or the manager who made the hiring decisions being axed.
Of course if the contract has this Vertragsstrafe that you have to pay if you don't show, then I would totally make them jump through all the hoops and get the money out of them for your two weeks. They'll almost certainly send you home right away, but they will still have to pay you.
Legally speaking4, if the contract does not state anything about them ending the contract before you start working, then they can do it. The BGB (common law) regulates when the notice period starts. In your case, that period is two weeks. It can either start from the date the contract was signed, or from your first working day. If nothing is in the contract to supersede that, the two parties need to find an agreement.
Anecdote: I've seen a company tell someone from abroad to not come to Germany because their contract will not start, a week before it started. It resulted in them suing the company and getting a relatively large settlement after a long time in court, because they had basically prepared to become expats and given away all their belongings and bought one-way tickets to Germany. If that is what is happening to you, get a good lawyer.
1) solicitor's website talking about legal precedent, in German
2) secondary source, in German
3) renominated newspaper, in German
4) relatively credible secondary source, in German