When can protection from creatures be played
They can play a card that gives their creature protection, but it is probably pointless if they are playing a card that destroys the blocking creature anyway.

In the combat phase there are 5 steps


Begining of Combat 
Declare Attackers
Declare Blockers
Combat Damage
End of Combat


During each of these steps each player gains priority and can cast spells/activate abilities if they want to. In your example the card giving protection must be cast at the latest in the Declare Blockers step, because the first thing that happens in the Combat Damage step is combat damage being assigned, which would deal lethal damage to the 4/4 and send it to the graveyard. However casting the card giving protection is pointless since with the 6/6 being destroyed there is nothing that will deal damage to it. Even though Protection prevents blocking once a creature is blocked removing the blocker or giving the attack protection does not stop the attacker from being blocked.