After looking around some more I found that someone from the Ubuntu community solved the problem by providing a special kdvi package which only includes kdvi and some libraries.
You can find the binaries there:
https://launchpad.net/ubuntu/intrepid/+ ... 0-0ubuntu1
(look at the far right side)
Since the .deb format is not readily supported under Fedora (at least I think so) I had to extract and install the contents by hand.
Long story short:
After installing this package and adding some dependencies (I don't remember exactly which ones) I am able to use the forward/inverse search of kdvi in combination with kile
