Hello! I'm a Canadian Pain Fellow!
So, in Canada, we now have a Pain Medicine residency, certified by the Royal College of Physicians and Surgeons of Canada. This is a 2 year sub-specialty residency to be done after a primary residency in anesthesiology, physiatry, psychiatry, internal medicine and I believe neurosurgery. There is a Royal College exam done after this residency giving fellowship status in Pain Medicine. This residency is offered in 6 sites across Canada - UBC, University of Calgary, McMaster, University of Toronto, University of Ottawa, and Western University. This residency started in 2014, so it's relatively recent. There are 9 spots across the country for this - pain medicine in Canada isn't nearly where things in the USA are at (far more interdisciplinary and less interventional here).
There are traditional one year fellowships that exist in a few programs in Canada, namely University of Toronto, McGill University and Dalhousie, but if you intend to practice in Canada, I think things are headed to the point where you will need the pain medicine royal college certification to practice here. These programs would take Americans (they take international fellows frequently), but the pain medicine residencies do not.
