Does Parachute Backup work with Advanced Data Protection?

Yes. Parachute Backup uses the iCloud account that is already signed in on your device, so there is nothing to turn off. Advanced Data Protection keeps your data encrypted in iCloud. Your copy is protected by whatever protects the destination, for example an encrypted drive.