Okay, so I have been struggling with this exact problem, and I fixed it by simply opening the Windows Firewall and unblocking Spotify from public and private networks. For some reason, there were two files named "spotify.exe" One was allowed on private, the other on public. I simply allowed both on both files and the files started syncing onto my phone.
I was about to switch to a different music provider for laptop and phone...
Tried deleting the cache... Almost deleted the app to reinstall.
Found this post. Changed the Windows firewall settings to allow Spotify (I also have 2 entries in the firewall settings) on domain and home networks for both files (currently on a home network, decided against allowing it on public).
Still wasn't working for local files even though downloads for "normal" Spotify songs were working.
Realize avast also has its own firewall and it was blocking Spotify. Set my network type to private on avast internet security and now mine are working as well.
Thanks for the tip in the right direction, btsheehy.