For hostel touring CX bikes should be fine. If you go camping, you may have to go ultra-light. Smaller panniers should solve the heel clearance problem.
Any modern brake is powerful enough for touring. My Shimano 105 calipers stop me with a big shopping load on steep hills, and I use them off road as well.
CX bikes tend to be more upright than road bikes, but you can change stems to suit.

For an alternative, consider a 26" MTB-wheeled light-touring bike.
UK makers Thorn do a series from heavy expedition tourer to fast city bike, with an excellent all rounder in between:

http://www.sjscycles.com/thornbrochure.asp

Bruce Gorden does an expedition version, but do any US manufacturers do lighter versions of this style?