Deleting Desktop Background Images
Okay I think I've figured it out. This was the recipe that worked:

Delete the Files


Reboot into recovery mode
Open the Terminal from the "Utilities" menu
csrutil disable as suggested by da4 (thanks!)
Reboot
mount -uw / i.e. mount the filesystem as writable
sudo rm -r "/System/Library/Desktop Pictures"/*


Restore System Integrity Protection


Reboot into recovery mode again
Open the Terminal from the "Utilities" menu
csrutil enable
Reboot