Первая заподлянка, с которой Вы столкнетесь - это авиабилеты. Так как города прилета и вылета у Вас различаются, то о чартерах и дешеВЫХ спецпредложениях придется забыть

Как не крути, но судя по всему Вам придется отдаться в потные лапки Аэрофлота

Не помню, летает ли Аэрофлот с юга Испании, но точно летает в Барселону и Мадрид. Билет Москва-Париж + Барселона(Мадрид)-Москва обойдется Вам несколько дороже, чем билет на регулярный рейс Москва-Париж-Москва.
Ну и можете еще сами поискать состыковочные рейсы ТУТА - единственный ресурс для бронирования авиабилетов через инет, позволяющий строить сложные маршруты.
Билеты лучше выкупать заранее (за месяц), есть больше шансов ухватить более дешевый тариф.

Далее. Поездом через Пиренеи Вы не проедите

Либо через Бордо и север Испании, либо через Марсель и Барселону. Но железнодорожные билеты на средние (по нашим меркам) расстояния в Европе пиздец как дорогие По скромным прикидкам, такая поездка в спальном вагоне (а сидеть всю ночь - зае@етесь!) обойдется Вам минимум в 250 евро на рыло. Так что имеет вмысл взять в рент машину и двинуть через Андорру, тем более что Андоррские красоты (и магазины!) стоят того, чтобы на них посмотреть.
Правда, и тут есть маленькая засада: Так как брать машину Вы будете во Франции, а сдавать в Испании - прямая Вам дорога в потные лапки ТРАНСнациАНАЛЬНЫХ прокатных контор - всяких там ХЕРтцев и Еврокаров. И на аренде машины в маленькой частной конторе тоже хрен съэкономишь

По гостиницам. Если Вы заранее и точно знаете свой маршрут - есть смысл подстраховаться и забронировать места в гостиницах заранее. Все это легко делается через инет. Но если желаете строить свое путешествие по настроению - то ночевать на берегу моря или под деревом в сквере Вам скорее всего не придется тоже. У меня по крайней мере проблем с поиском свободных номеров не возникало ни в Андорре, ни в Испании. Хотя опять-таки находить вы будете не самые дешевые гостиницы.

Так что резюмируя вышесказанное - если есть достаточно денег, то подводных камней быть не должно.

ВизоВЫХ ограничений никаких нет, Шенген он и есть Шенген. Равно как и нет пограничных постов на "границах" Франция-Андорра и Андорра-Испания. Впрочем, их не было и в дошенгенские времена

Если есть еще какие-то вопросы - задавайте!