OK, I finally got it to work.
I downloaded the backup into a VM and used mysqldump to save the database. I deleted the gradebook category entry. And again saved the database. I used a diff program to spot the changes between the two databases and it seemed as if only one relevant table was affected, namely mdl_grade_categories.
So, I backed that up, then copied that table from the backup to the broken version and after some foostering, it all seems to work.