Running wp-cli on a website that was set up by somebody else resulted in a strange error:

PHP Parse error:  syntax error, unexpected '?' in phar:///usr/local/wp-cli.phar/php/wp-cli.php(23) : eval()'d code on line 1
Error:
<h1>Fehler beim Aufbau der Datenbank-Verbindung</h1>
...

The database settings in wp-config.php were all correct and WordPress was also working, so this did not seem to be the problem. In the end, I found out the reason was a byte order mark at the beginning of wp-config.php that had been inserted probably by Windows Editor. To solve the issue, the easiest way is to open the file in a good editor, for Windows I recommend PSPad, copy everything into the clipboard (CTRL +A, CTRL + C), create a new empty file (CTRL + N), paste everything (CTRL + V), save it (CTRL + S) as wp-config.php and upload the file.