I faced the same issue of Firebase cloud messaging not received by device.
In my case package name defined on Firebase Console Project was diferent than that the one defined on Manifest & Gradle of my Android Project.
As a result I received token correctly but no messages at all.
To sumarize, it's mandatory that Firebase Console package name and Manifest & Gradle matchs.
You must also keep in mind that to receive Messages sent from Firebase Console, App must be in background, not started neither hidden.