According to https://forum.kde.org/viewtopic.php?f=251&t=152383 Okular bookmarks are stored in .local/share/okular/bookmarks.xml (in Kubuntu 18.04 at least). Okular seems to relate stored bookmarks to PDF files base on the file's path, so if one moves a file which already has bookmarks, the bookmarks break (because they are still pointed at the previous file path).
In order to fix the bookmarks one can simply open the bookmarks XML file and do a quick search/replace to update the stored paths to point to the new location of the PDF file.