We don't know that this was not done. We do know that the dog tracking was not covered by any news photographers because there weren't any pictures of it; that may well indicate that LE managed to evade the media that morning.
As to searching an entire town randomly, I can see a few problems with it. For one thing, dogs are animals and not machines. Casting for scent is hard work and, particularly in hot humid weather conditions, can cause a tracking dog to overheat. General practice is to take the dog or dogs to the victim's last known location and start from there so that the dog doesn't have to cover any unnecessary ground.
Another problem is that gas vehicles and their exhaust are known for dulling a scent dog's sense of smell. That's why handlers get to a location and then take 15-30 minutes to walk the dog around (carefully avoiding any possible areas of scent) before starting. I don't know of any reputable dog handler who will claim that their dog(s) are 100% reliable on tracking a victim that has been transported by vehicle. There are some flimflam artists out there that make such claims but let's ignore them.
Finally, I think what would have happened had this been done is that the dogs would have given mild alerts all over town. Anywhere the girls went in the previous week or so would have been alerted on. The problem with that is that it wasn't a question of whether the girls had ever been there. The problem was: where were the girls after their last known position?
Would it even be possible for dogs to track the girls if they were on their bikes? Without them having physically touched anything?