Nachtrag: Der Fehler tritt übrigens auf, wenn ich eine Produkt in den Warenkorb lege, weiter zur Kasse gehe und dann nachträglich die Zahlungsart ändern möchte.
Nun den Shop auf 5.1.6 geupdatet. Fehler nach der Bestellung (/checkout/finish) der selbe wie oben beschrieben. Und ja, Cache, mehrmals komplett gelöscht.