Assuming that this is KDE, you should be able to go to Start > Settings and click "Menu Updating Tool", then click "Scan". It should find your new game, and you can put it somewhere in the menu.
You can also go into Start > Settings > Menu Editor and move the menu item around, or create a new item under Games. The actual path to the game executable goes in the box "Command". You can find the path by opening a shell and typing "whereis nameofgame" (you don't type the quotes when you do this), then hit Enter. So typing "whereis kasteroids" gives you "kasteroids: /opt/kde/bin/kasteroids". The Command is /opt/kde/bin/kasteroids.
Let me know if this works. I am on Slackware, but KDE should be the same in Fedora. Good luck.