Das sieht alles ganz richtig aus. :-)
Du hast in Paypal dein Bankkonto angegeben?
Ist das zur Lastschrift freigeschaltet?
Normalerweise fragt der Apple Server nur kurz nach, ob das von Paypal seiner Seite aus klargeht.
Kommt grünes Licht geht es los. Es gibt zwei Möglichkeiten. Entweder von Paypal kommt kein grünes Licht oder der Apple Server weiß nicht wo vorne und hinten ist. Hast Du versucht Paypal mal auf einem richtigen Rechner unter appleid als neue Zahlmethode einzusetzen? Manchmal nimmt das System nichts von iPhone und Co. an.
Das kann z.B. an Datenmüll in Safari liegen.
Eine weitere Möglichkeit ist das deine Bank übersehen hat das Du dein Konto zu Paypal freigegeben hast. Auch das kann passieren. Bei meiner Bank musste ich kurz anrufen um meine Kreditkarte zu nutzen, von sich aus haben die sich nicht gemeldet. Das hat meine Kundenbetreuung wohl "aus versehen" weggeklickt. :-s
Probieren könntest Du auch, von iTunes und App Store kurz abmelden und ohne dort angemeldet zu sein unter deiner Apple ID die Zahlmethode versuchen zu ändern. Ich glaube dann wäre man wirklich alles durchgegangen was möglich ist. Check das nochmal ab. An sich erfüllst Du alle Grundvoraussetzungen das es gehen sollte.