"Hime" itself isn't purely an honorific, as was already noted. "Hime-sama" is probably the most common way for subjects to address a princess in the Japanese language. In fact, it'd probably be a high offense to address a princess as "Hanako-hime" rather than "himesama" were they a commoner and the situation took place in feudal Japan. Someone familiar with a princess might say "Hanakohime-sama" when trying to be especially deferent. But addressing royalty is really, really complex; at its base level it's because the royal title is considered part of their formal name. I've used all of these stylings when addressing princesses with Saiga because he's supposed to be a Yamataian samurai aristocrat, so would definitely do that stuff.
Similarly, since "heisho" is not purely an honorific form of address, "heichou-san" wouldn't be particularly out of place within a military unit. Kinda like saying "Gunny" or referring to someone as "THE Sarge" instead of "Gunnery Sergeant Dudebro." It's important to remember that -san, -sama, etc don't translate directly to mr. or mrs. or ms. They're different levels of respect in the Japanese language. Those "translations" are just the closest approximation.
I agree on not doubling up honorifics, though. For example, SAINT director Nakaide Shida could be called "Shida-sama/san" or "Shida-bucho" (Director Shida) or "Shida-chujo," but wouldn't ever be called "Shida-bucho-sama" or "Shida-chujo-bucho." But he might be called "bucho-sama" (the director) or "chujo-san" by a fellow admiral that doesn't know his name but can see the rank (or someone familiar being patronizing).
You can basically add an honorific to any word except a word used as an honorific (i.e. Neko-chan is fine).
But, as people have said in the past, "Yamatai isn't Japan" so do whatever makes y'all comfortable.