Can you choose Missandei as your discard for Marched to the Wall? If she were "immune" to discard effects I don't believe she could be chosen, but since it's "choose and discard" the choosing would seem not contingent on whether the discarding would be successful.

No.

"Choose and discard" means "discard a target character." The choosing is not some separate effect; it is the targeting part of the single discard effect. The definition of "cannot" says that "cannot be discarded" characters are not legal targets for discard effects.

So, Missendi cannot be chosen as your character for Marched to the Wall. She is not a legal target for the effect. You have to choose another one of your characters. If you have no other characters, you don't choose anyone.