I've installed my distro yesterday and then spotify-client. But no icon appeared, this can be a workaround if you have a similar issue.
1. Your device and operating system: Desktop PC (AMD FX-6300) - OS: Debian 9.5 (4.9.0-7-amd64)
2. Type of Spotify account you have (Free/ Premium): Premium
3. The app version of Spotify you’re using: spotify-client 1:18.104.22.1680.g51b03ac3-13
4. Brief description of the issue: Spotify's icon not appearing.
5. Steps to reproduce the issue:
a) Just install the distro
b) Then install Nvidia controllers (version 390.87) and cinnamon desktop (version 3.2.7-4).
c) The icon is missing but you can start spotify using your terminal
FIX: Once i created a symbolic link, the icon appeared. No need to restart cinnamon btw.
ln -s /usr/share/spotify/spotify.desktop /usr/share/applications/