Under the Agreement on Internal Trade (AIT), there shouldn't be any medic exams. There could be an exam on things of provincial legislation and/or local protocol. The whole point of the AIT (chapter 7)is to allow free movement of workers accross the country. If you are registered/licensed in one province other provinces have to accept your registration/license.
Quebec's EMS system is not something I'm familiar with. Check with the juristiction or company you plan to work for.
Check out the PAC website. http://www.paramedic.ca/
If I were you, i would call urgences sante, the montreal ambulance company. From what Ive heard you have practicals, a protocol exam and a physical aptitude test. You obviously need to be fluent in french. As for AIT, i dont believe it really applies in quebec as the system is totally different. For example PCP is higher scope of care than ambulance techs here. hope this helps. If you need any more info send me a message. Id be more than happy to help you out