Any size water change can help, but it is not always a simple percatage drop. Example 100ppm with a 50% change doesn’t always mean new reading at 50 ppm.
So I read about your age, and the tank size, the skimmer used. My question is on maintenance and mechanical filtration.
Skimmer: Remora Pro are cool. I myself still have the Remora myself. Have you descaled the pump and unit? Within the last year. I ask because unlike most skimmers the Remota line(AquaC) is an induction skimmer. Sprays a jet of water in to create your foam engine. As pumps age and skimmer due to calcium deposits effect not only pump performance but foam column. You may need to descale the unit to increase performance. Don’t forget to unscrew the set screw inside of skimmer housing to access the injection nozzle. Also you can find the manual online: AquaC Remora Pro
The pump if I remember right was a Magdrive 3 or 5
Water changes: it may be less distributing to conduct smaller water changes more frequently. Turn off flow to the aquarium and with a turkey bastet or powerhead attempt to suspend accumulated detritus from the rocks and behind the rocks. Allow to settle then siphon clean sand and pockets of detritus. Replace
Fresh water in a manner with the minimial disturbance.
You probably will have an outbreak of some form as recortrecting such a high NO3 is going to create some imbalance in bio-filter.
NOPOX as stated is carbon dosing. Start slow, if you go this route. By slow I mean 1/4 of recommended dose slow. You can increase as you see change but 1/4 dose reduces fuel for a bacterial bloom. “It is easy to add sugar to your drink, but removing sugar is much harder.”
Lastly, remember that your problems took a while to develop, it will take a while to correct.