Em primeiro lugar, seria melhor se você nos dissesse por que você quer bloqueá-lo em primeiro lugar, deve haver uma solução melhor para isso. Também Spotify (Free) requer acesso à internet para trabalhar (a menos que os arquivos locais sejam reproduzidos, mas então porque não usar o Media Player?), Então não tenho certeza por que você quer fazer isso ...
Qual antivírus você está usando? Alguns softwares antivírus têm firewalls que substituem o Firewall do Windows.
Por exemplo, eu uso o AVG e, em seu firewall, posso configurá-lo para bloquear o Spotify assim:
Após bloqueá-lo e iniciar o Spotify, o bloqueio funciona porque ele não pode se conectar à Internet.
Isso deve ser possível com o Firewall do Windows com Permitir um aplicativo ou um recurso no Firewall do Windows .