Você está correto de que pdfsig não está no poppler-utils que vem com 16.04. No entanto, está em poppler-utils de 16.10 e posterior.
Se a compilação do poopler 0.65 for concluída com sucesso, você poderá executar pdfsig fornecendo o caminho para o binário compilado. Provavelmente, você pode encontrar o caminho executando find . -type f | grep '/pdfsig$' no diretório de compilação do poopler. Então você acabou de executar ./path/to/pdfsig <options> <PDF file>
Como alternativa, você pode instalar os utilitários pop-up dos pacotes 16.10. Você precisará baixar os arquivos deb do aqui . Basta procurar por 0.44.0 ou 0.48.0 e fazer o download do caminho certo para sua arquitetura (provavelmente i386 ou amd64 , se você estiver em uma arquitetura x86 de 32 bits ou 64 bits). Você não precisará de todos os pacotes correspondentes. Execute dpkg-query -l |grep poppler para encontrar os nomes dos pacotes que você deve baixar.