Así como se indica en [esta respuesta][1], debes poner en el cuadro de búsqueda `Windows Service` y te aparecerá el elemento para crear el nuevo proyecto. Por alguna razón que desconozco no se muestra el elemento en el panel de la parte izquierda.

  [1]: https://stackoverflow.com/a/30689355/3200493