Thanks for all the really helpful replies. The most interesting one so far is @poeliev’s suggestion of the Payback Visa Flex⁺ Kreditkarte. Although its earning rate is very poor at €5 = 1 point (compared to €1 = 1 point with my existing Amex card), it nevertheless contributes to a Payback points balance that I’m already collecting with Amex, rather than creating another points balance for a different purpose.
The reason that I don’t want to pay an annual fee is that I live in the UK and my expenditure in the Eurozone is sporadic. If I was living in the Eurozone and spending in EUR every day, then I would consider paying an annual fee for a higher earning rate, like I currently do with my GBP-denominated Miles & More cards.