Automator Localization issue?
You can change the time format by setting LC_TIME to fr_FR:

LC_TIME=fr_FR exiftool -v '-Directory&lt;DateTimeOriginal' -d ~/Pictures/Photos-Sources/APN/%Y/%Y-%m\ %B/%Y-%m-%d\ %A -r "$f"

$ LC_TIME=C date +%A\ %B
Monday November
$ LC_TIME=fr_FR date +%A\ %B
Lundi novembre


Terminal and iTerm 2 set LANG (which changes LC_TIME) automatically based on the region selected in System Preferences.

On my installations of 10.8 and 10.9, the Run Shell Script command uses the C locale by default though.