And credit cards in Germany are not "credit" cards as well. At least the one I got from Sparkasse does not let you hold a balance and must be paid in full every month.
Not sure about those, but I got mine around 2-3 years ago from gebührenfrei.de, which is from Advanzia Bank. Seems fine so far…with a minor disclaimer that I don’t really use it much. :-)
I don't have enough experience to speak about CC in Germany, but I don't see why a Rewe or ... boh, Aldi, Mcdonalds, etc should prevent that. I am a bit surprised, to be honest.
Debitcards, not girocards. I have no girocard since years, and still can easily pay everywhere. But to be fair, the pandemia really pushed this even the small shops.
Not true. It probably depends on the location, but last time I paid for a public service, I had no problem using my Visa Debit Card. I think it was not even possible to use cash.