iCloud includes purchases from the iTunes store that were made with a different Apple ID

Unfortunately I don't have an answer, but I did want to reply with what I've found so far in my own research.

I just purchased a new iPhone XR and after opening the box to set up the phone, I decided to use the "Transfer My Device" feature to copy all of the data from my previous phone, which is an iPhone 6s.

I experienced the exact same thing. Except in my case, I chose to "Skip This Step" and decided to stop what I was doing after the fifth Apple ID which I have never seen before appeared in the "different Apple ID" prompt.

I have been the single owner of the iPhone 6s and since buying it new in store, I have only ever used my Apple ID (which is my current Apple ID) to download anything. I know that for a fact. So this is very strange.

I can not find anything directly from Apple regarding this phenomenon.

So far all I can come up with is the following two threads:

This one from August of 2019 (https://discussions.apple.com/thread/250559320)

And this one from January of 2019 (https://discussions.apple.com/thread/250079070)

It seems that the after King_Penguin's response in the August 2019 thread...

The only ways for another account's content to get on the phone is directly logging onto that account on the phone and downloading content from the store, or syncing content from that account from a computer's iTunes library.

And Eric Root's response in the January 2019 thread...

Based on what you have posted, I don't have an answer to your question. If all the apps on the phone are in your purchase history as you posted above, I don't understand why any better than you do.

That was where both discussions had ended.

There were suggestions about how to review your purchase history and what to do if you think your Apple ID has been compromised but neither of those are applicable to me.

I use two-factor authentication with my Apple ID, in addition to routinely checking my purchase history for all of my accounts (not just my Apple ID) and I receive text alerts every time that my one and only card is used. I've never used another payment method with my Apple ID.

I will continue to research this and reply back if I can find any more information, though I have little hope since beyond those two dead-end threads my searching thus far has turned up nothing.

What I did, and what I feel is the best thing you can do for now, is as follows:

1. Considering the weekly nature of data breaches these days. I think it can't hurt to change your Apple ID password but as Eric suggested, you should read this page first to understand what you'll need to do after changing said password.
2. Consider enabling Two-Factor Authentication for your Apple ID if you haven't already done so.
3. Visit the following website and check to see if the email address associated with your Apple ID has been comprised: https://haveibeenpwned.com/
4. If you use the same email address with any other online accounts / services, do what you can to change those accounts' passwords as well.
5. Contact Apple Directly as it is your best hope of getting a response from someone within the company. I will be doing so.

Hope this helps to some degree