Does the Medic need to wait until their next turn to remove cubes when another player researches a cure?
The blue cubes in Paris are removed immediately:

From the Rules (Classic Pandemic p.5), emphasis mine:


  The Medic removes all cubes, not 1, of the same color when doing the Treat Disease action. If a disease has been cured, he automatically removes all cubes of that color from a city, simply by entering it or being there. This does not take an action.
  The Medic also prevents placing disease cubes (and outbreaks) of cured
  diseases in his location. The Medic's automatic removal of cubes also
  happens during other players' turns.