Check with the card providers that Apple Pay is supported, and your cards have been approved for use with it. Many card providers have a (phone) security setup stage before phone payments can be accepted to the card account.
Yep, went through that too. Kohl's was one of those. They had to text me a code before it would take it. It was all set up, but still didn't work.