The colour shift is probably not related to the bit depth (8 or 16), but more likely to the gamut of RGB vs CMYK.
As far as I'm aware, when Photoshop refers to 8-bit or 16-bit colour, it's talking about each channel, so 16 bits is plenty for individual colour channels in RGB, and won't be the cause of changing colours (if it was 8-bits shared between the three channels, probably using a colour palette, it'd be ugly, but at least in my experience, Photoshop talks in bits per channel).
The CMYK gamut is different to the RGB gamut, and it's probably just the conversion between the two that causes the colour change. This article on gamut is probably a good place to start understanding the concept. The basic problem is that the colour spectrum isn't really just combinations of R, G and B, and projected/printed colours can only cover a part of the actual spectrum that our eyes can see.
The problem with converting between CMYK and RGB (in either direction) is that there are some colours that can be represented in one, but not in the other. The strongest/brightest reds, greens and blues that can be shown on an RGB device or represented in an RGB format simply cannot be created from a CMYK device/format. Likewise, the strongest cyans, magentas and yellows from the CMYK gamut will not be accurately reproducible on an RGB device or in an RGB format.
When you display a CMYK image on your RGB monitor, you're effectively limiting yourself to only the colours which both gamuts can reproduce (the monitor cannot go beyond its physical RGB limitations, and Photoshop is algorithmically limiting the colours to the CMYK gamut).
So if you're trying to apply a strong red, green or blue to the image, it simply cannot exist in the CMYK format and so won't show up as you expect on your screen, since Photoshop is converting the RGB colour you've picked to the nearest CMYK colour available. It's worth noting that if you print the image, it'll appear much like the CMYK version (you cannot print the strongest Reds, Greens and Blues your screen can show).
If the image is only for on-screen viewing, then convert to RGB. If it's for printing (which I would assume is why its in CMYK format?), then you're not going to be able to print those colours outside the CMYK gamut anyway (unless you can print with Pantone colours instead).