Why do airlines follow these routes between Barcelona and Düsseldorf?
Large parts of France's airspace are designated military training areas. If there is military flight training going on, the choice of routing over France is very limited. The only option is to fly around these areas, which  results in the routes you found. 

Higher altitude route map of France courtesy of EUROCONTROL[PDF, 8MB]

Since the PDF seems to be giving problems on some computers, I've combined several screenshots and drew the approximate route of your westerly flight (in yellow), the planned flight of GWI 9525 (blue) and Temporary Segregated Airspaces (TSA's) in red onto the map. The crash location of GWI 9525 is marked by a red/yellow star.
 

Note that not all the TSA's in the map are actively used at all times and that in some cases crossing is allowed but altitude restrictions apply.

In addition to active TSA's there are other considerations that come into play such as weather and airway capacity &amp; demand. If you have to wait 15 minutes longer for a slot on the shortest route, you might as well fly a slightly longer route if that allows you to depart earlier.