Contacts don't sync from phone to Google

Search This thread
Hey guys,

so as the title suggests, my 5X doesn't sync the contacts with the Google servers.
All the other things are syncing just fine.

I've found a number of different suggestions on the internet, but none of them worked so far.

Things I've tried:
* Install a different version of the contact sync app
* Clear the cache of play services and contact sync app
* Clean all the apps of old urls or strange strings (HTC sync relicts, etc.)
* Install the Google contacts app

I also found that you can clear the data of the contact store app, but I didn't try this as I feared loosing my contacts.

Does anyone have an idea how to get the syncing working?