Też miałem problemy z Android Pay.
Wydaje mi się, że wynikają one z faktu, iż często na telefonie mamy zainstalowane aplikacje Bankowe (MBanak itp.), które to staja się aplikacjami domyślnymi również do płacenia. Powoduje to konflikt z Android Pay.
Mi udało się rozwiązać ten problem poprzez przeinstalowanie Android Pay. Po jego "pierwszym" uruchomieniu pojawiło się pytanie, czy ma to być program domyślny do płacenia. Po wybraniu opcji "TAK" wszystkie problemy z funkcjonowaniem tej aplikacji minęły.