You can't do that.
A Windows service is a non-interactive process. It cannot display any user interface, because it's not part of an interactive session. Therefore, it can't respond to window messages, because it can't have a window to receive them.
Stick with an application which starts when the user logs in. If you want the user to be able to trigger the shortcut even if your application isn't active, you would need to look at using a global keyboard hook:
A Simple C# Global Low Level Keyboard Hook[
^]