As mentioned in the post, I would have thought that Germany would have learned from the Belgian experience when Belgian newspapers tried something similar and ended up getting de-indexed.
They couldn't force a Google to index German news sites. Or rather, they could, but Google could just leave Germany and the risk of Google pulling out completely from Germany would be pretty high.
Plus, it's not clear how this would work from an EU point of view... could Germany dictate what an Irish company had to do, and then charge a tax on that operation?
Or course, Google could also index the German news sites, but then penalize them so heavily in scoring query results that they'd never appear. Problem solved! In the index? Yep! Appearing in a search result? Nope!
The idea of forcing a search engine to index particular sites just starts to get into the realm of silly. Then again, your should never put it past a government to do something silly.
I think these German sites believe that they're entitled to be paid by Google, and they'll view any action that Google takes to avoid paying as an illegitimate loophole which they will try to close. If framed as an antitrust issue (Google's using a search monopoly to put newspapers out of business), forced indexing might not seem like an unreasonable remedy. Remember that this is the same country that believes book prices should be fixed by law.
If search engines could neither index these sites for free nor leave them out of the index, the German law would be amount to little more than extortion.
