I use a locale 'de_DE' WordPress version.
The month is translated correctly, but the weekdays should start on Monday (Montag) and should be localized Mo, Di, Mi, Do, Fr, Sa, So.

I believe this is inherited from the ReactDatePicker component. If so, we'll need to figure out how to pass localization through. I believe this is where the names are being generated: https://github.com/Hacker0x01/react-datepicker/blob/master/src/calendar.jsx#L273-L281
_This ticket was mentioned in Slack in #core-editor by jeffpaul. View the logs._
Related to #1311
One user just pointed out in a support ticket that he expected the date-picker to adhere to the "Week Starts On" - choice

set via WP-Admin > Settings > General.
When it's set to Monday, the date-picker in Gutenberg also should start on Monday.
Also reported here #9109
Tested and confirmed that strings in the date picker (and also the "Status & Visibility" sidebar panel) do not appear to be translated even though the strings do appear to have translations at https://translate.wordpress.org/ (such as "Status & Visibility" and "October", though I couldn't find the option to translate short weekdays like "Fri" in a search).
Result: strings such as "October" that have translations at https://translate.wordpress.org/ do not show up as translated in the date picker and strings for short weekdays such as "Fri" do not appear to have entries at https://translate.wordpress.org/ at all.

Seen at http://alittletestblog.com/wp-admin/post-new.php with site language set to de_DE (screenshot) and profile language set to site default language (screenshot) running WordPress 4.9.8 and Gutenberg 4.2.0-rc.1 using Firefox 63.0 on macOS 10.13.6.
@Soean are you seeing the same thing? and are these now two separate issues that should be filed separately?
Yes, I see the same, we don't need a separate issue.
The datepicker has changed since I reported the bug, but it is still not localized.
When a post gets scheduled or published, the shown date under "Publish" is also not localized.
Gutenberg 4.3
WordPress 4.9.8
I'm looking to see if we can localize the datepicker