In order for Non EU based airlines to run flights either into or inside EU airspace then they need both route licenses and bilateral agreements with the specific countries involved. The fact that Air Canada isn't able to run flights from London or Rome to Paris would indicate that this is not an Air Canada/EU issue but an Air Canada/French government one.
Nope
In or out of an EU airport to/from country of origin is a bilateral
Between airports not of the country of origin is single market access. Canada (which I just picked as an example) doesn't have single market access, if we don't negotiate it than the same issues start to apply to our airlines and EU ones
Brexit is not simple, the devil is always in details the public and politicians here and in the EU didn't want to think about but will bite them in the bum if they don't watch it.
In the case of any airline based outside of the EU trying to purchase route licenses into France even from other airports within the EU would still end up 'requiring' a 'bilateral' agreement for one very important reason. The largest French airline is Air France-KLM and is part owned by the state (I believe the current stake is somewhere between 15% and 20%). Given that there are already a number of examples of the French government ignoring EU laws and regulations (Shengen comes to mind straight off the bat as the Calais camps would never have existed under the terms of the agreement because the occupants would have already been settled elsewhere) do you really think that France wouldn't put it's own interests first.
But getting back to what I initially said, and I may be being overly optimistic here, but anyone in the EU with a hint of common sense connected to the Route licenses will see an immediate and massive economic impact from shutting down flights from the UK, and even more so when in response the CAA airspace is restricted. To give you an idea of how big an impact it will be, a flight from Paris to Washington DC is currently around 6200km but without access to UK airspace and having to reroute via say Madrid you end up travelling around 7150km instead, a flight from Berlin to Washington DC is around 6720km and going via Madrid would add approximately 1860km. Given the additional operating costs I can't see the airlines being able to justify this economically so you will most likely end up with a much smaller number of transatlantic flights from only one or two airports, having looked at the CAA map I'd say most likely flying from Madrid or Barcelona as you can arc flights from those two airports around UK airspace fairly easily without adding too much to the flight duration.
If that was to happen, given the State of Spain at the moment this could (and quite likely would) have a massive negative impact on the economies of France and Germany. Rampant unemployment and a government desperate for an influx of capital would make relocating business from Paris, Berlin and Munich to name a few a far more tempting prospect for a lot of multinational and global businesses.