In Craft 3, how to clear stuck "Deleting Stale Template Caches"
The answer was, to delete the first row of the queue table in the correct database.
Also, it helped to increase max_execution_time in /etc/php/7.1/apache2/php.ini