OK, I now know what made the the Page not Found problem start… because I have the exact same site installed in another folder (same template, same plugins, etc. but in another language). As soon as I visited my permalinks page on that WordPress installation and the error mentioned above appeared at the top of that page.. then the 404 pages started showing up.
I don’t know how to stop it except selecting the Default permalinks settings, which I don’t want…