I dont know if that is still relevant. But i faced the same issues for days. I cant really say what it was. But here is what i did.

• I created a new key in the apple developer section.
• Added the key in Firebase Cloud Messaging in my iOS App.
• Added my AppStore ID
• Turned on production mode in Firebase
• Created a new private key in the Service Accounts Tab in Firebase
• Added the private key in server

Cant really what it was. But i tried everything before. Nothing seemed to be working. Maybe this will help someone.