In Dominion: Adventures, does the discarded Traveller have to be in hand, or can it have been played?
From the rulebook, bottom of p5: 


  When a player discards a Traveller from play, he may exchange
  it for the card indicated.


Your hand is never considered to be "in play":


  "In play" - Action cards and Treasure cards played face-up to a play area are in play until they are
  moved somewhere else—usually until they are discarded during a Clean-up phase. 


So discarding it from your hand does not do anything; you must play it and then discard it from play at cleanup to trigger the exchange. You do not pay for the upgraded card - the upgraded version has a cost only because of the many cards like Remodel that care about a card's cost.