There are two reasons to tie the left shoe first, either because the gemara in shabbos 61a says 'the same as tephilin, so too with shoes'. It is disputed there whether or not to do this at all, with many rishonim ignoring this practice, the Rambam for instance. But Rabbeinu Yona, brought in many achronim says a Yorei shomaim should do this, being that the Torah gave Kavod to both sides, the right side for placing of blood for a Metzora and chalitzah, and to the left side as we tie Tephilin on the left arm. The Levush gives another reason to compare shoe tying to tephilin being that in chulin 89a the mitzvos of tzitzis and the retzuos of tephilin were given to Avraham's children as a reward for him telling the king of Sedom 'from a string to a shoelace'. The Mishna Berurah and Pischei Tshuva say concerning gloves which need tying, that is not to put on the right first and tie the left first, being that according to the reasoning of the Levush, this din only applies to shoes.
It would seem after all is said and done, this also only applies to laces, not other means of fastening.
Also even according to the simplistic reading of the gemara and Rabbeinu Yona, velcro would have no place in the laws of tying Tephilin, and as such should not come in to the discussion.