Ich kann leider nicht mehr nachvollziehen warum der Fehler auftauchte. Auf jedenfall wurde immer ein Fehler mit „Missing \begin{document}“ und einem Zeichen, das so aussah „�“, ausgegeben.
Ich hatte bei Kile eingestellt, dass er das Unicode BOM (Byte Order Mark) hinzufügen soll. Anscheinend kann PDFLaTeX das nicht.
Seltsamerweise funktioniert das Kompilieren bei nochmaligen Anlegen der Dateien mit BOM…
Naja, auf jedenfall habe ich die Version ohne BOM behalten. Um die ersten 3 Bytes aus der Datei zu entfernen kann man wunderbar „dd“ benützen.

Dateikopf vorher:

hexdump -C test.tex 
00000000  ef bb bf 25 20 2b 2b 2b  2b 2b 2b 2b 2b 2b 2b 2b  |...% +++++++++++|

Hier mit „ef bb bf“ zu sehen ist der BOM.

Mit „dd“ enfernen:

dd if=test.tex of=test2.tex skip=3 bs=1

Dateikopf nachher:

hexdump -C test2.tex 
00000000  25 20 2b 2b 2b 2b 2b 2b  2b 2b 2b 2b 2b 2b 2b 2b  |% ++++++++++++++|

Alles wunderbar, weitermachen :).

Nachtrag:
Außerdem ist jetzt der „Fehler“ weg, dass die erste Seite des PDF Dokuments immer leer ist. Habe schon danach gegoogelt und Andere mit ähnlichen „Problemen“ gesehen. Vielleicht hilft’s dem Einen oder Anderen weiter?