I've been struggling for the past month to sign up. I am based in South Africa and seeing very similar behaviour as many on this thread:
I'm using a card which works just fine in App Store
Contacted support, which tells me my bank is declining the transaction
Contacted my bank, who has no trace of the transaction and hence the decline
Back to support who tells me to try another card
Rinse, repeat
Eventually I asked for the case to be escalated, pointing the support engineer to this thread. There is clearly a systemic issue with Apple's card processing here. My guess is that Apple's acquirer / card processor is declining the transaction because Apple is not asking for, and hence not sending, the CVV of the card, whereas in the App Store they do ask for the CVV.
Anyway, after escalation they asked me to send proof of ID, and two days later the transaction went through, using the exact same card details that was declined previously, i.e. still no CVV.
It seems like escalating the matter to a senior support engineer did the trick for me. Hope this helps someone else as well. I am pushing the engineer for answers as to why it finally went through with the same details as previously, but have not received a reply yet (will update here if I do receive one).