Categories=Qt;KDE;Graphics;Office;Viewer;
to read
Categories=Qt;TDE;Graphics;Office;Viewer;
so simply changing this entry from KDE to TDE will result in the menu entry being start -> Programs -> Accessories -> Office -> Okular which seems more logical to me.
I also found smtube had the same issue and was resolved in the same way. I would think any KDE package is likely to create the same type of menu entry so this could be used for any package that looks out of place.
To find the location of the desktop file you could issue the following command (change okular for the package you want to find)
locate okular | grep desktop
This relies on installing mlocate (or similar) and then using the command sudo updatedb to refresh the location information beforehand.
Hope this can be useful to anyone who dislikes menu entries being weird (like I do)
EDIT:
Anyone using the Plasma desktop might find this does not have the intended effect although I haven't tested it.