Sunrise in Paris is crucial, because that's the moment we know where the sunrise is, and how fast it's moving west.
But no, it's not at all simple. My very, very crude approximation is probably in the ballpark, but you have to realize that the sunrise travels different speeds at different latitudes, the terminator is not perfectly north/south (in fact, this time of year as we head into the summer solstice, it's nearing 23ish degrees to the pole).
Worse, the plane isn't flying along a line of constant latitude. It's a great circle route. What you want to find is the point on the route where the elevation of the sun matches whatever your definition of "dark" is. In this case, I chose start of civil twilight, 6 degrees below the horizon.
This probably has no closed form solution, and requires an iterative solution. I admit the calculations above are a mess, but they essentially attempt to do your "plane travels east, sun travels west" idea, with some reasonable assumptions about the time the plane starts, the time the sun starts, how fast each is travelling, and when we consider them to have met.
Actually, you could set this up fairly easily with an astronomy library.... Generate points along the great circle route and get the elevation of the sun at each step. It's been a few decades since numerical analysis, but a simple binary search looking for the desired solar elevation ought to converge really fast.
I was tempted to stay up and watch flight aware and the global day/night map and see how close I got, but... meh.