Why doesn't Automator service appear in iTunes?
To get it to work in iTunes, you can try setting it up like this:

Service receives selected: text in: iTunes

Actions:

"Get Selected iTunes Tracks" - Get selected: tracks

"Open Finder items" - Open with: VLC