The first thing that I'm going to say is test and then test some more.
If I'm thinking through this correctly you should be able to use your initial plan with a slight modification in the steps. I would go; Intune Phone -> iCloud Backup -> Enroll New Phone in Jamf -> Restore New Phone from iCloud Backup.
You may need to change your Prestage to allow for restoring from iCloud and also ensure that the new device is set to your Jamf server in ABM.

Option 1 should work as well but I would also modify that work flow to enrolling the iPhone in Jamf and then restoring the device from the iCloud backup as you go through the setup wizard. 
One thing to note is that the app icons and the app data will be on the device but the apps will need to be downloaded from the same app store that they were purchased from originally.

Thanks. Yeah, we've been testing, but (of course) we're also in a valley between user upgrades this month, so the real-world cases haven't been as frequent as we'd like.

We know from testing that if you don't first remove Intune management (before an iCloud backup), you will have issues. Jamf and Apple both confirm that if you back up a device that's enrolled in MDM, that MDM enrollment is retained in the iCloud backup.

Again, the process that seems to work is:

Intune phone -> Remove Intune Mgmt -> iCloud Backup -> iOS Setup on brand-new phone -> iCloud Restore in Setup -> Jamf Enrollment .

Re Apps: For end-user phones, we pay for the service, manage them for Security, and very little else. Our concern is getting the apps procured by users (with their accounts) to install in the location they expect, and they're not having to move apps back into place.

It's been quite a while since I've had to do a mass migration from one MDM to another. A couple of years ago we migrated from Xinca, which is now Jamf School, to Jamf Pro and most of those where migrated while keeping the same device so the workflow isn't quite the same.

I figured that the serial number change between the old device and the new device would break the carry over of the MDM data. From what your testing is showing and I have a faint memory of things working the way the you are describing, I think that your workflow is the only way that will work the way that you want it to.

All,
I had an extensive call with a Jamf Escalation Engineer (Ty) yesterday. His response:

"According to your conversations with Apple, it does also sound like we should remove the old MDM profile first before taking the initial backup.

I'd be curious to see if that step is necessary, but it is probably a good step regardless to make sure the support desk understands the migration of management to the new server."

Our tests DO indicate that this works. We'll be actively monitoring this on the next few phones, and I'll update if anything changes, but it does seem like we have a solution.

Hey folks, closing the loop on this original question.

Summary: When taking an iCloud backup of an Intune-managed device, wiping the device, and preparing to enroll the same device into Jamf, we're prompted to restore from iCloud, but then the MDM enrollment screen (into Jamf) never appears.
We got a clearer answer from Jamf this week. I've tested the "more intensive workflow" referenced below, and it does seem to be accurate.

[...]
"I'd like to point out this article from Apple that states, "When you restore from a backup onto the same iPhone, iPad, or iPod touch, your supervision state is restored from your backup. If you restore from a backup onto a different iPhone, iPad, or iPod touch, your supervision state comes from Apple Business Manager or Apple School Manager." 
[...]

When you try to restore from a backup the device will grab the MDM configuration profiles from the previous time it was backed up i.e. when it was still enrolled into Intune and will not be correctly enrolled into Jamf as devices can only be enrolled into one MDM at a time. It's best to skip the restore from backup screen during the set-up assistant and instead direct users to then log into iCloud on the device to sync Contacts and Media. This requires that there are no restrictions in place from Jamf that would prevent logging in to iCloud.

There's also a more intensive workflow for this as well but it does require a second device:
1. Take an iCloud backup on Device A, which has all the photos and data we want to keep.
2. Restore that iCloud backup to Device B, and check to see that the data has been restored successfully.
3. Take an iCloud backup on Device B.
4. Go through the workflows to add Device A to Automated Device Enrollment and enroll in Jamf.
5. During Setup, restore the iCloud backup taken on Device B. It is important to restore the backup from Device B, not Device A.
6. The device should now be enrolled in Apple Business/School Manager and Jamf, with the photos and data from the backup.