This question is now resolved. It is not a bug, but a server misconfiguration. I am adding the resolution here for posterity.
It turns out the issue was caused by the server being set to Europe/Berlin, but PHP-FPM defaulting to UTC.
Setting PHP-FPM to Europe/Berlin through its configuration file solved the issue.
Welcome to SE! Setting up cron can be confusing since there are many variations and it touches several aspects: OS users & permissions, CMS users & permissions, other tools, cron - and the details depend on your hosting environment.
I've just re-read the page you linked to. It has the information you need, but it also has other options that you ...
Welcome to SE! The error includes /bin/sh^M: bad interpreter. The ^M part suggests you created the file on a Windows machine and copied it to your Linux server. Linux and Windows have different conventions for marking the end of a line. See this for more explanation.
For are many ways to fix that. If you have ssh to the Linux box try running this to ...
I just set it up with dreamhost shared hosting.
I went into cron jobs in my dreamhost control panel and added a new job.
under command to run I put
"/usr/bin/php /home/DREAMHOST-USER/EXAMPLE.COM/wp-content/plugins/civicrm/civicrm/bin/cli.php -u WP-USER -p WP-USER-PASS -e Job -a execute"
Obviously leave out the quotation marks and change all the sections in ...
It turns out cv is the only way to go on drupal8. Drush 9 is not supported yet and the web invocations don't work due to the split paths of the civi install.
If it only works for you when invoked directly and not from cron, check its output. I was hitting a somewhat buggy php test. You have to make sure php runs in cli mode.
EDIT: Official docs updated.