From Gideon's Avenger 's Gatherer page:
"If an opponent's creature enters the battlefield tapped, Gideon's Avenger's ability doesn't trigger."
July 21, 2014 2:05 p.m.
The key thing is that "becomes XX" means "goes from not XX to XX". In your example, the creatures entering the battlefield were never untapped before being tapped.