If Okular can’t use the links immediately after starting up, but it starts working again after Okular’s state is “jiggled” a bit… that really sounds like something that would need a bug report.
Actually I might have found one, but it looks like it never got investigated very closely… https://bugs.kde.org/show_bug.cgi?id=398113
If that’s what this is, then it seems there’s been some weird little bug lurking around for quite a long time…