Particleboard anywhere in a rigid tile floor installation can wreck the tile job. Atmospheric and seasonal changes are enough to ruin the tile. Please DO NOT allow any particle board to remain. Oriented Strand Board (OSB) is however a different story and is acceptable.
Removing the staples isn't difficult but it certainly can be labor-intensive. The best way to remove them is to first use a heavy scraper, most of them will come out. The ones that won't can be removed one at a time using a pair of end-cutters or side-cutters. You could even snap them off and then hammer the remains back into the floor.
As far as repairing the subfloor...it just depends on how much damage you are creating. Sometimes the thinset used to set the cement board is enough to repair small divots. If you are adding another layer of plywood maybe you shouldn't worry about minimal damage to the subfloor.
How about a picture of the damage?