My first thought it to turn to your Gmail account. Somebody would have to have access to that in order to verify your account with Apple.
When you say Apple did not let you change the questions, what exactly happened? Several years ago Apple transitioned to using two factor authentication instead of security questions. You can continue to use security questions if you already use them and they are working for you, but if you have problems then they no longer get direct support. You can try the directions in this support article If you forgot the answers to your Apple ID security questions - Apple Support but the article is labeled "archived" and may contain information that no longer applies. If the instructions work then fine; if they do not (e.g., you see “not enough information”*) then you will have no option but to change to the newer security method, if you can. Over the past few years Apple has been persistently encouraging users to switch to the newer two factor authentication security system. For those who have disregarded their encouraging, Apple will likely only help you to now change to two factor authentication, if even that is possible. Follow the instructions in the "Turn on two-factor authentication for your Apple ID" section in this support article --> Two-factor authentication for Apple Account - Apple Support to try to change to two factor authentication.
If you still need help, contact Apple Account support at this link ➞ https://getsupport.apple.com/?caller=cups&PGF=PGF63005
Select "Other Apple Account Topics", then "Security concerns or account compromised." This will give you a chat or telephone call option.
If Apple cannot, or will not, help you transition to two factor authentication then it is quite possible you will have to simply abandon the old account and everything it contained. In that case, if you were using the Find My service, the Activation Lock support request support article at: - https://al-support.apple.com/#/additional-support may at least let you regain use of your equipment. If not, you will also have to say goodbye to the device as well.
In general something is odd about this whole thing. An account created with security questions would have to have been created several years ago when Apple was still using them (all accounts since are required to use two factor authentication). Why only notify you now? Are you sure the notification is really from Apple? Read this article about identifying real App Store and iTunes Store emails --> Identify legitimate emails from the App Store or iTunes Store - Apple Support Sometimes the only indication in a communication is very subtle. Have a look at this thread. Someone registered an Apple ID with my em… - Apple Community It can be very hard to tell from a communication alone if it is authentic. The best way to check is to use an independent way through Apple's own resources to confirm what the communication claims. Scams (e-mail, text messages, and phone calls) are getting very good at closely imitating true Apple communications. Always be cautious.
*More about identity verification problems here —> Cannot Reset Security Questions - Apple Community
