Well, by reading the text I'd always assume that Sharra checks before Shrine: Sharra "ignores" damage and the Shrine redirects damage "whenever damage would be dealt to you or a creature you control, it's dealt to this structure instead". Sharra ignoring 4+ damage leads me to the expectation that there would be no damage dealt, hence nothing to be redirected.
Protection, on the other hand, reads: "The next time this creature would take damage, it ignores it and loses protection instead."
If "this" creature is Sharra, then no damage would be dealt, if it's 4+. Same goes for the wording of Shrine. Hence, I consider it a bug.
If "this" creature is anything else, then I'd say Shrine's text ("you or any creature you control") is more open/global than that of protection, therefore redirecting it, leaving no damage that would now be dealt to "this" (specific) creature.
I admit, though, the latter might as well go vice versa. Hence, maybe a bug, maybe working as intended. Couldn't tell. It could depend on what was in the board first, the protection or the shrine.
After all, I'd think it safe to assume that Sharra, Shrine and Protection should be checked in this order:
- Sharra - 4+ damage? -> Ignore, don't check further.
2./3. Shrine - Any damage left? -> If yes, redirect it to the shrine.
3./2. Protection - Would this creature still take damage? -> If yes, pop the protection first.