I understand that healing in another Starting town works the same as if you heal up in your own town. You have to spend weeks but you get a bonus.
Movement and encounter deed are two separate things. The thing is that, after you move you have to make a encounter, pvp or healing. But is not included in the movement.
The rules state that you cannot heal after moving (e.g., page 23).