Don't worry about the repair permissions output. You are always going to see a bunch.
At this point I'm running out of ideas. To summarize, you get the problem when:
1. You boot in safe mode. So that means it is not related to the various start up items.
2. You cleared the relevant caches (hopefully). So that is not the cause.
3. You check language preferences and have the proper settings.
The only stuff I think that's left are preference files (plists). There's so many of those finding the bad one(s) is problematic. Frankly the name of a plist that could screw up only Finder menus doesn't come to mind. You already tried com.apple.finder.plist so that one is out of the running.
Here's a radical suggestion/experiment:
What if the entire ~/Library/Preferences directory was renamed and an empty one created in its place? This might indicate if it is an errant plist for sure before trying to go out on a "search and destroy" mission (I like to call it that) trying to find a specific plist.
My only concern is that caching might cause the bad plist to be recreated when you log out.
I would recommend you back up your entire system to another drive. Then rename the Preferences directory on that backup and create the empty one in its place. That gets around the caching concern. I am assuming your home dir is on the same disk as your boot dir. So now safe boot off the backup. When you log into your account it won't have any plists in the Preferences and it will create new ones as needed.
Note, because there aren't any preferences this might "break stuff" if you try to use that stuff. That's why you need safe mode for booting. You only want to use the account long enough to see if the finder menus are stilll screwed up.