Así como se indica en esta respuestaesta respuesta, 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.