Parece-me que o aplicativo tem o gargalo. Eu acho que use apenas um thread para converter os pdfs.
O Tomcat executa servlets em paralelo, mas quando os servlets chamam uma biblioteca de um encadeamento, seu aplicativo da Web se torna um aplicativo de um encadeamento. Você precisa modificar seu aplicativo para usar mais threads.
Uma solução não muito boa está executando tantas instâncias do Tomcat quanto o núcleo que você possui e fazendo o balanceamento de carga das solicitações para elas (como você mencionou na pergunta).