Does the Medic remove all cubes of cured diseases from the cities he travels through?
All of the cubes. This is not an action.


  The Medic may remove all the cubes of a single color (instead of 1)
  when performing the Treat Disease action. Also, if the Medic at any
  time finds herself in a city that contains cubes of a disease that
  has been cured, she may immediately remove all of those cubes.  This
  unique ability is in effect during all players’ turns and does not
  cost any actions to perform.


Emphasis mine.