Normally I use rings made out of lulavim to tie around the Lulav on Sukkos. Would rings made out of velcro be fine for this purpose?
Yes. While R'Yehuda holds "lulav tzorech egged" (they need to be tied), and therefore one must use part of the 4 minim to tie it, the halacha is not like R'Yehuda. Thus you can use anything to tie the 4 minim, or nothing at all. In fact, the Gemara says the anshei Yerushalayim would use gold to tie their lulavim.
Even though its not required, we have a minhag anyways to tie it to make it look nicer, and that may be the reason we used dried lulav to do that also. Though I would think gold and perhaps velcro are nice enough also.
In the Shulchan Aruch HaRav 651:3 he writes that you may do so. And in :4 he writes that it is permitted to even hold that other material when holding the lulav.
However in :5 he cautions that if the extra material is not being used to actually bind the lulav it can be considered a chatzitah. I think this is the reason that it is avoided - just in case it comes loose, or the extra thread after the knot.
Machloket Rabbi Meir an Rabbi Yehuda in 3rd chapter mishna 8: we pasken as Rabbi Meir who allows outside of 4 minim. The reason is that tying is not an obligation for RM so tying material is not a part of the mitsva and tying with a fift species is not bal tosif, a prohibited addition.
Summary: Good 100%. Lechaora no matter to hiddur.
The mitsva to make a knot for RM is itself mishum Hiddur, ze keli veanvehu. See SA OC 651, 1
ומצוה לאגדם בקשר גמור, דהיינו ב' קשרים זה על זה, משום נוי; ויכול לאגדם במין אחר.