Tried on OS X 10.9 and windows 8 on two differents networks. Tried reinstalling app (both on nexus and on OS x). With My old s3 mini the devices was found, and the feature works, except for the local files playlist
Normally I'd be suggesting disabling all firewalls, antivirus and security software on the PC and making sure that UPnP is enabled on the router but the fact that it doesn't show on two networks and an old phone does doesn't fit. Maybe try those things anyway? Also make sure that the Nexus works otherwise over wifi and double-check that spotify isn't in offline mode (I know, I know).
Something magic happened, today when i have opened the spotify desktop app, Nexus 5 appeared in my Devices. Wow.
Unfortunatly the "local files" playlist continue to be not synced with the phone.
When i check the playlist, it appears "in sospeso" on the image ("pending", in italian) of the playlist, but it never starts sync.
I've tried to check another playlist and the syncronization has started immediately.
OS X 10.9 with Spotify for Mac 0.9.7.16.g4b197456 and iTunes 11.1.3
Nexus 5 with Android 4.4.2 with Spotify for Android 0.7.4.610.gd7332b3
I am a Spotify Premium user
If i go on "Local Files" under "My Library" from the desktop app, i can see correctly my iTunes Library (i have checked only iTunes as source for Local Files) and i can listen the songs without problems.