iCloud recovery

Did she already sign into iCloud.com/find that only requires her Apple ID and password, no verification code, to mark the phone as lost?

You cannot recover an Apple ID using two factor authentication without knowing the trusted phone number. She’ll need to check with prior carriers, friends, family, etc. to figure out what that phone number she used was.

Two factor authentication no longer uses prior account security questions and the owner of the Apple ID is in full control of the Apple ID on their end, Apple does not help you recover it from their end.

once she figures out that trusted phone number she had used she will start account recovery. While their online support article says for forgotten password, account recovery steps are also for a new phone number if you can’t sign in to update the number.  See manage your trusted phone number at  https://support.apple.com/en-us/HT204915#trusted and How to use account recovery when you can’t reset your Apple ID password - Apple Support 

When going thru the account recovery steps need to first enter in that old number to show you know it. Then when you get to the step where it says it sent a code to that old number select the option most like “didn’t get code” and it will let you continue with your current number.

Always scroll down for additional options in small blue print if the  ones showing don’t apply to/work for you.

When starting the account recovery steps the credit card is an extra option and not required. (See prior tip)

Account recovery is a two phase process once started. Phase 1 is the evaluation period, usually 24-48 hours but can be longer or shorter. This phase says Apple is evaluating your info and you’ll get an update after the posted time is over (people mistakenly think it means they’ll be able to reset the password immediately after this first phase.)

Once phase 1 is done it enters phase 2 where https://iforgot.apple.com/ will give you the final amount of days (can be weeks) you’ll wait. On that final day you’ll get a text, follow that text/email immediately.

Unfortunately no. Paying or not she’s the only one who can do anything about it by figuring out that Trusted Number. Removing her devices from her iCloud Find My was the wrong move, the entire point of Find My is so you can put the devices in Lost Mode so it can’t be used by anyone else. As soon as you signed out on every device she stopped having them as trusted devices so she could get a verification codes and/or update her trusted number along with now allowing whoever has her iPhone the ability to erase and use it for themselves.

Only thing a Apple can do is cancel the paid iCloud subscription so she’s no longer charged. This also means she loses her saved data so don’t do this unless she is 10000% certain she will never remember that phone number.