I found a solution which uses ImageMagick, but it took me a while to figure out that I had to use the option
-page A4 to generate an A4 formatted PDF. In the end this simple command did the trick for me:
convert *.gif -page A4 book.pdf
While googling for an answer I realized that other people also have tried this, and encountered problems which I never saw. These hints may be helpful to some of you.
Images of different sizes: If your images do not all have the same size, have a look at this YouTube video: “How to convert multiple images to A4 pdf using imagemagick”. The guy in the video uses the command (which he states produces A4 output):
convert *.jpg -resize 595x842 -gravity center -background white \
-extent 595x842 resultimage.pdf
This question has been brought up on stackoverflow, but closed as off topic (“How can I convert a series of images to a PDF from the command line on linux?”). As this gave me a hint, but not the full solution I'm creating (and answering) this question here, in the hope that someone else will find it useful, too.