For starters, shoe laces need to be tied, and they come undone. To use Velcro straps you simply have to press them firmly into place, and they take quite a lot of force to undo improperly.

The fact of the matter is the primary reason most people, by a huge margin, chose laces over Velcro is aesthetics (which Velcro sorely lacks).