Das sieht nach einem Problem mit Realurl aus, falls das installiert ist. Am besten sollte Realurl auf dem Warenkorb Seiten deaktiviert werden.
Oder ist unter Paypal eine Rückleitungsadresse eingetragen worden? Auch im Shop Setup sollte man nichts festlegen, damit der Shop alle für Paypal notwendigen Links selber generiert.