Make sure you have the correct thread credentials on the Android.
On the Android Companion App open Settings → Companion App → Troubleshooting (I think that is what it is called in english, but it list logfiles and other tools to diagnostics as description of the item).
In this next window click the Sync Thread Login Credentials (Again it might not be named exactly that, but close to and there should not be that many options and it should be in the bottom)
It should say either something with “Added …” or “Already using the same credentials”.
The trick here is to run it again and make sure that it does not say “Added …” the second time.
If it does then you need to clear the Google Play Services Cache, which might clear a lot of other stuff, like login to services and credit card informations for Google Play and websites and so on, so make sure you know you informations before hand.
The way to clear the cache is Settings → Apps → See All Apps → Google Play Services → Storage and Cache → Manage Storage → Clear All Cache
Now repeat the syncing of the thread credentials above.