The debug log unfortunately did not really help me.
Interestingly, when I deactivated sync for all 6 task lists (keeping only the address books activated for sync), the problem disappeared. However, regardless which of the task lists I subsequently re-activated, I always got the sync problem. I then purged tasks (within Horde) that had been completed more than 30 days ago – no more synchronization problems. But current tasks no longer appeared on the smart phone either! Luckily, when I now add new tasks, they appear both on the Android device as well as inside horde.
So, long story short, did not find the cause of the problem, but was somehow able to solve it (with side effects though – would have liked to keep the current tasks on my mobile.