Hallo Eguino,
die Meldung „Card added to Apple.com/Bill“ bedeutet zunächst, dass die Karte als Zahlungsmethode hinzugefügt wurde. Wenn sie kurze Zeit später trotzdem abgelehnt wird, würde ich das Problem nicht allein bei der Speicherung von Ablaufdatum oder Sicherheitscode vermuten.
Prüfe bitte einmal unter Einstellungen > [dein Name] > Zahlung & Versand, ob Name und Rechnungsadresse exakt mit den bei deiner Bank bzw. dem Kartenanbieter hinterlegten Daten übereinstimmen.
Da du die Karte bereits gelöscht und neu hinzugefügt hast und PayPal funktioniert, würde ich die Karte nicht immer wieder neu einrichten. Wenn die Daten stimmen, wäre der nächste sinnvolle Schritt, beim Kartenanbieter nachzufragen, warum die Belastung von Apple abgelehnt wird. Apple selbst kann den konkreten Ablehnungsgrund in der Regel nicht sehen. Gegebenenfalls muss der Anbieter die Zahlung oder bestimmte Online-/internationale Zahlungen erst freigeben.
Dass der Sicherheitscode erneut abgefragt wird, würde ich für sich genommen noch nicht als Hinweis darauf werten, dass die Karte nicht richtig gespeichert wurde.
Viele Grüße
PreCognition