Once a creature is blocked, then it doesn't matter if it is given protection. That creature already has a status as a blocked creature. The protection will prevent any damage Knight Exemplar would deal to card:Gideon's Avenger, but it won't suddenly cause Gideon's Avenger to go around the Exemplar and hit you.
Protection follows the DEBT acronym:
Damage - All damage that would be dealt to a creature with protection from X by a source of quality X is prevented.
Enchant/Equip - A creature with protection from X cannot be enchanted or equipped by anything of quality X.
Blocking - A creature with protection from X cannot be blocked by a creature of quality X.
Targeting - A creature with protection from X cannot be targeted by a source of quality X.
When protection refers to blocking, it means that a creature of quality X cannot be assigned to block a creature with protection from X. If the attacker gains protection after becoming blocked, it has no effect as far as the B in DEBT is concerned.
509.1h An attacking creature with one or more creatures declared as blockers for it becomes a blocked creature; one with no creatures declared as blockers for it becomes an unblocked creature. This remains unchanged until the creature is removed from combat, an effect says that it becomes blocked or unblocked, or the combat phase ends, whichever comes first. A creature remains blocked even if all the creatures blocking it are removed from combat.
702.15f Attacking creatures with protection cant be blocked by creatures that have the stated quality.
Does the situation change if the attacking creature had trample? And the blocker was destroyed or the attacker had gained protection from its color?
If the attacking creature gains trample, it still has to assign lethal damage to the blocker, but it can potentially do damage to the defending player.
If the blocking is destroyed after being assigned as a blocker, then the attacking creature is still blocked. If a would-be blocker is preemptively destroyed before the declare blockers step, then it won't be around to block regardless.