Start melee AI for the player, it does a sufficient job with search and destroy as long as you do not have pathing islands (in which case it starts to cause frames to be dropped). Make sure they have enough that they would not be defeated in melee and that you do not accidently defeat them, this is to stop them from potentially giving up.
In StarCraft II this is even more easily done by just ordering the spawned units to "suicide" which causes them to mercilessly, and without regard to their lives, hunt down every single enemy unit on the entire map. Warcraft III should also have such a mechanic for its campaigns but I am not knowledgeable enough with WC3 AI to know about it.