It's wild that users have to be psychic enough to figure this out.

It's a super daggy solution, but I've found being humble and putting a little message in the app to let users know of oddities goes a long way. E.g. "To download this song, you need to make it part of a playlist" would have been enough. Inconvenient for users wishing to download a song for offline listening, daggy for spotify's UI, but much better than the status quo of frustrating users.