In reality, it's up to you. Do whatever works and looks best, no matter what that is—don't blindly rely on numbers or automatic conversions.
Generally what you want is to find colors that match as closely as possible. Pantone colors are specifically designed for faithfully reproducing single colors, so choosing a Pantone color and sticking to that is a good way to go. Pantone itself gives conversions to CMYK and RGB of its colors that you can use, they're normally pretty spot on but there's nothing stopping you from coming up with your own values.
Keep in mind that RGB has a bigger gamut than CMYK* so there are colors you simply cannot reproduce going from RGB to CMYK (as you have seen). Pantone similarly has many colors that you simply cannot achieve in CMYK. There is nothing stopping you from using those colors and choosing as similar a CMYK color as you can, but be aware that there will be noticeable differences depending on the medium, which obviously isn't ideal. Or you can pick colors that are comfortably within the gamut of RGB, CMYK and Pantone and have consistent colors, but you are then limiting your choices (the easiest way to do that is to start with CMYK).
As with many things, it comes down to compromise. At one extreme you have the perfect color that you unfortunately cannot faithfully reproduce, and at the other extreme you have consistent colors that are dull are boring. Hopefully there is a happy medium.
But, as I said before—it's all up to you (Not only is it up to you but it is specifically your job to make that decision. Just make sure you can back up that decision with solid reasoning).
* Comparison of some RGB and CMYK colour gamuts on a CIE 1931 xy chromaticity diagram.
Source: http://commons.wikimedia.org/wiki/File:CIE1931xy_blank.svg
