I checked how many calendar entries I have and it is ~5500 distributed over 5 calendars. That does not sound too much in my ears. So what to do now?

Indeed. Can you please post the logs as a gist so that we can be sure where the problem is? According to my calculations, ~ 30.000 entries (in 1 calendar) should be the limit.

The next goal for DAVdroid is to integrate it with ical4android. In the course of this, the sync. algorithm will also be overhauled. It seems reasonable for me that the deletion could be split into more transactions because it’s not an incosistent state when some entries are already deleted and some are not.