Первое приведенное Вами правило — о сложных словах с начальной частью, заканчивающейся на согласную, поэтому к словам с частью вело оно не подходит. Второе было бы применимо, если бы часть вело присоединялась к слову, пишущемуся со строчной буквы, например: велогонки, велобаза, велоспорт, велотренажер. Если же нужно присоединить приставку или первую часть сложного слова к собственному имени, пишущемуся с прописной буквы, то нужно руководствоваться правилом координации. По нему правильно писать вело-Россия, вело-Уфа (аналогичные примеры из правила: спорт-Одесса, фото-Москва). К сожалению, без учета орфографического правила было зарегистрировано название общественного движения «ВелоРоссия».
Приставка пара... пишется слитно. Правильно: паравелоспорт.