I’ve lost the iPhone that I had bought iCloud storage for

Add your old number from web account see a thread How to find my phone - Apple Community

To set up old iCloud account in new iPhone .

The Apple ID say example1@icloud.com exists on server and you know the password and its account credentials , however that is signed in the device iPhone .

If you don't remember the trusted number and yet it is verified in the account , visit your cellular service centre with personal identification proofs , the number can be obtained from them .

If the account is set with two factor authentication from iPhone .

Issue a sim on behalf of the same number and insert the sim Set up cellular service on iPhone - Apple Support

In a new iPhone that is purchased Turn on and set up iPhone - Apple Support

The Apple ID and password is active so is the 2FA active on the iCloud server , once a new trusted number is added the code will start appearing on the new trusted number , and the person can access the account .

See the article Get a verification code and sign in with two-factor authentication - Apple Support

Then access the account and remove an old inactive verified number from the account .

Go to your Apple ID account page and enter your Apple ID and password.

In the Security section, click Edit.

Click Add a Trusted Phone Number. 

To add a number, enter the phone number and verify it with a text. 

To remove a number, click cross sign next to the phone number you want to remove. 

Note : you don't need account recovery from the server as Apple ID and password are known to you How to use account recovery when you can’t reset your Apple ID password - Apple Support

You need to add card details Add a payment method to your Apple ID - Apple Support

Beastlerma1977 Said:

"I bought more storage from I cloud and the device I bought it on is lost, but I want to use and have it connected to my phone now."

-------

Accessible Purchase Storage:

Internal storage cannot be upgraded. It is what it is. So, the maximum internal storage capacity never increases, even if you upgraded your iCloud plan. All you need to do is enable iCloud Drive in iCloud Settings on a device. Learn More here: What's the Difference Between Device Storage and iCloud Storage? Apple Support