Encontrei uma solução que usa o ImageMagick, mas demorei um pouco para descobrir que precisava usar a opção -page A4
para gerar um PDF formatado em A4. No final, este simples comando fez o truque para mim:
convert *.gif -page A4 book.pdf
Solução de problemas
Enquanto procurava por uma resposta, percebi que outras pessoas também tentaram isso e encontraram problemas que eu nunca vi. Essas dicas podem ser úteis para alguns de vocês.
Imagens de tamanhos diferentes: Se suas imagens não tiverem o mesmo tamanho, dê uma olhada neste vídeo do YouTube: " Como converter várias imagens para pdf em pdf usando imagemagick ”. O cara no vídeo usa o comando (que ele afirma que produz saída A4):
convert *.jpg -resize 595x842 -gravity center -background white \
-extent 595x842 resultimage.pdf
Postamble
Esta questão foi colocada em stackoverflow, mas fechada como off topic (" Como posso converter uma série de imagens para um PDF a partir da linha de comando no linux? . Como isso me deu uma dica, mas não a solução completa, estou criando (e respondendo) essa questão aqui, na esperança de que alguém a ache útil também.