One anomaly is that there is no option to clear the list of recently opened documents from the menu. Even clearing the most recently used list from the KDE 4 Menu does not clear the list within Okular.
It comes down to having to manually edit a file. The file in question can be found in your home directory.
Using my PC as an example, the file can be found at;
Close Okular first. Edit this file and delete the lines under [Recent Files]. Save the file, then restart Okular.
If anyone knows an easier way to achieve this, please let me know!