Tum_Puh, выбор небольшой. Ездил в Краков несколько раз из Прешова. Ну и из Ужгорода дорога пойдет все равно через Прешов.
По горам-по долам и будет. Вот один мой рассказ:
http://www.kirpet.ru/2011/12/solyanye-kopi-velichki/ Тут мы ехали в Величку, но это рядом с Краковом. Это на Стару Любовню, Мнишек над Попрадом - Пивнична Здрой - Новый Сонч. Ну это ваш вариант
Или другой вариант: Прешов - Чирч - Мушина и т.д.
Или: Мушинка - Тилич далее везде...
Но в общем хрен редьки не слаще.
Один раз мы по ошибке поехали чрезе польский Закопане. Это Прешов - Попрад (тут плюс: автомагистраль), потом в горы на Ждьяр и далеее в Закопане - тут горы по полной программе.
А вот дальше от Закопане на Краков идет очень неплохая дорога. Но это немного крюк. По времени дольше, но дорога приятна (кроме пересечения Татр).
Так что на ваш выбор...