This is going to sound very odd (I think it's a bug), but adding the Routing>agent>onqueue permission was what caused the Voicemail PIN option to show up in Preferences in my org.
Better answer:
Currently, until a new feature gets turned on for Production, the Voicemail PIN setting is enabled for Communicate users by giving them the "General>Unified Communications" permission.
The Engage User role also grants the needed rights to see the setting.