Está correto eu ter dois projetos "exe" em uma solução que use a mesma biblioteca de classes?
Sim, é super normal. Inclusive, eu já participei de um projeto que tinha 5 executáveis e mais alguns projetos web na mesma solução.
Ainda existe a opção de fazer várias soluções com apenas alguns .csproj, não acho que isso é interessante pro seu caso.
Se tiver interesse nisso, é só criar uma solução em branco e adicionar os projetos existentes que você quer nessa solução. É uma abordagem que eu tenho visto bastante quando o escopo do projeto muda drasticamente. Como, por exemplo, uma solução contendo tudo pro sistema principal e o projeto com as classes compartilhadas, outra solução com tudo pra interface web de gerenciamento do sistema, mais as classes compartilhadas e outra solução com os projetos mobile e mais as classes compartilhadas.
Hoje conforme eu preciso testar, eu vou e marco a aplicação como "startUp Project" e depois faço a build. Existe uma abordagem tecnicamente melhor para isso?
Não sei se é tecnicamente melhor, mas ainda é possível executar vários projetos ao mesmo tempo. Indo no menu Debug > Start new instance