For Red Wedding, the reason the "other" character can not claim power is because the second "choose" can not resolve. This is due to the fact that the game disallows choosing a "can not be killed" target to be killed. You are presented with a situation where both targets are disallowed by the game, therefore disallowing the action of choosing. With no choice, there is no "other" character.
Also, the reason the player to the left gets to make a choice is because they are not making a choice for which the resolution is a kill effect. They are making a choice for which the resolution is for another player to make another, different choice.
For House Umber Berserkers, the situation is similar. You are required to choose a character for which the resolution of the effect is that the character is killed. The choosing and the killing are resolved as one effect with the choosing being the initiation of the effect. This means that the effect is not satisfied if you attempt to choose a character that can not be killed as the game does disallows that choice. If the choice is disallowed, the effect is not satisfied and you "must" satisfy the effect which forces you to choose a target that is not Beric.
With regards to "Choose a character. Then, kill that character." The issue is with the initiation. Choosing a character is an initiation effect. It is not a resolution effect. Therefore if you were to take the "Then" as a true "then" effect it could never resolve. There is no action that resolves successfully for the "Then, kill that character" to succeed. So for this card to work the text must be interpreted as "Choose and kill a character" or some variation of it,