If I was to attack with a character that has deadly and my opponent defends but uses an effect to save the character, does that effect save the character from both the deadly effect and the military challenge?

Claim and Deadly are two completely separate kill effects that even initiate separately. Therefore, you would need to save the character from both effects separately. You need two saves.