I just installed k3b myself (after looking for gnomebaker and not finding it...), and likewise it wasn't on the menu. I added a gnome menu to my top panel, which is where I've added some quick launch icons and a weather widget and there wasn't an entry for k3b there either.
I opened a terminal and typed in k3b and it came up for me, so apparently it'll run. Then I closed it and pulled up alacarte (menu editor) which you can actually get to by right clicking on the Menu and selecting 'edit'. I found k3b was showing in the 'sound and video' category but the checkbox was blank, so I checked it, closed and now k3b is on the menu! HTH.