No. If two creatures have protection from each other, they still cannot block each other or bypass each others' protection.
If a creature has protection from red, that means only that it can't be DEBT:
- D ealt damage by red sources
- E nchanted, equipped or fortified with red auras, equipment or fortifications
- B locked by red creatures
- T argeted by red spells or abilities
And that's it. Protection falls under none of these criteria, and so is not itself protected against by protection.
Protection from everything means:
702.16i: "Protection from everything" is a variant of the protection ability. A permanent with protection from everything has protection from each object regardless of that object's characteristic values. Such a permanent can't be targeted by spells or abilities, enchanted by Auras, equipped by Equipment, fortified by Fortifications, or blocked by creatures, and all damage that would be dealt to it is prevented.
... which still doesn't cover the protection ability itself.