Eu me deparei com esse erro enganoso também. No meu caso, o log do console indicou:
okular(30121)/kdecore (trader): KMimeTypeTrader: couldn't find service type "okular/Generator"
Please ensure that the .desktop file for it is installed; then run kbuildsycoca4.
okular(30121)/okular (app) Okular::Document::openDocument: No plugin for mimetype '"application/pdf"'.
Como instruído, eu corri o kbuildsycoca4:
~% kbuildsycoca4
kbuildsycoca4 running...
kbuildsycoca4(30132) kdemain: Reusing existing ksycoca
kbuildsycoca4(30132) KBuildSycoca::recreate: Recreating ksycoca file ("/var/tmp/kdecache-tmetro/ksycoca4", version 205)
kbuildsycoca4(30132) KBuildSycoca::createEntry: new: "okularGenerator.desktop" in servicetypes
kbuildsycoca4(30132) KBuildSycoca::createEntry: new: "libokularGenerator_xps.desktop" in services
kbuildsycoca4(30132) KBuildSycoca::createEntry: new: "okularEPub.desktop" in services
kbuildsycoca4(30132) KBuildSycoca::createEntry: new: "okularPlucker.desktop" in services
kbuildsycoca4(30132) KBuildSycoca::createEntry: new: "libokularGenerator_fax.desktop" in services
[...etc for several screen...]
Depois disso, o okular conseguiu carregar PDFs.
Parece um bug de embalagem. Isso deve ter sido executado em um script de pós-instalação.