States each player "must" exhaust 1 hero to travel here. Meaning if all heroes are exhausted from questing travel is not possible?

Yeah, you have to pay the cost. When it's worded like "Do X to do Y," the X is the cost.

If it had been worded "After you travel here, exhaust a hero," you could get away with going there even if everyone is exhausted.