Only someone from the Spotify payment team can explain why they are no longer accepting this payment method but have you looked to see if you can buy a Spotify e-card using this payment method? That might be a way around this for you.
Get in touch here and one of our support team will get back to you as soon as they can. You may be best writing in German as our German speakers know the most about Sofort/Klarna payments. If you get an automated response, reply back to it directly.