Добрый день! На мой взгляд, очень хорошая у Вас идея, единственное, для однодневного пешего трека Мельк-Кремс - это много, да и смысла особого я не вижу, а вот какой-нибудь этап вот отсюда
http://www.donau.com/en/wachau-nibelung ... terbesteig - просто замечательно.
Вот здесь можете посмотреть этапы для велосипеда -
http://www.donau.com/en/wachau-nibelung ... bike-path/И пешеходный и велосипедный вариант - очень популярны. Есть даже предложения недельных туров, когда Вы проходите этапы пешком или на велосипеде, а Ваш багаж перевозят с одного места ночлега до другого.
По поводу проката велосипедов можете посмотреть nextbike.at, например. Там можно взять в одном месте, а вернуть в другом. В Вахау этих мест довольно много. Еще неплохой вариант взять электровелосипед, наверняка есть возможность или в Мельке, или в Кремсе, тогда больше успеете. Момент, который обязательно нужно учитывать, - замки обычно на горе, Агштайн вроде как на скале, и я сейчас подробно не смотрела, подразумевается ли в описаниях по ссылкам выше эти подъемы. Вполне может быть, что нет, а для подъемов вообще лучше бы горный велосипед, в общем, нужно посмотреть это повнимательнее. Парковки для велосипедов в Австрии - обычное дело, это не проблема.