Oh lord, pet stores do love to treat axolotls like fish, dont they?
Okay so the BIG thing about black worms (and also why they are hard to find) is that they can sometimes have LEACHES in them (eww), which are obviously quite dangerous for your axolotl. They can look a LOT like the black worms too. Just make sure you keep an eye out.
So, the person who told you that live plants will increase your nitrates? Never ask them for advice again. Maybe also talk to the store owner. That person has no place in a fish store. SMH. So the way the cycle works, as I believe someone mentioned, is axies make ammonia, which beneficial bacteria convert into nitrites. Both ammonia and nitrites are hella toxic. Well...kinda. There are two types of ammonia and both your pH and temp affect it, but...that's more complicated than we need to be right now. The last stage is nitrates which are not as toxic but will continue to build up until removed. Removal can be done by water changes or by plants; for plants, Nitrates are a fertilizer and they LOVE them. Try some java fern, marimo moss balls, or duckweed...note that last one can be problematic as it was cover everything that touches the surface of your water. Given that your TAP WATER comes out at 30 ppm....you need live plants. Also, on a side note, that has me concerned for YOU. Drinking that much nitrates is not good. It also means you are getting fertilizer\sewage into your water, which I assume\hope is a well? You might want to look into that for your own health:
"A nitrate level of up to 3 ppm in well water is generally believed to be naturally-occurring and safe for drinking. The U.S. Environmental Protection Agency (USEPA) has set the primary drinking water standard (from public water supplies) for nitrate at 10 ppm."
So...even with a Nitrate from the tap at 30 PPM...for it to be getting to 120 ppm with 30% water changes every other day? That is an increase of 90 ppm PLUS the 30% you are removing. That means your ammonia is being built at a shocking rate., yes it is being converted, but it is still really problematic. When you are feeding frozen especially, are you removing the uneaten bit? Frozen needs to be fed very carefully, into a dish with a turkey baster so it doesnt go everywhere and then the uneaten has to be removed. You also arent seeing poop....so either he isnt producing it, or he is exploding it before you remove it...which STILL wouldnt account for that huge a spike I would expect. You need to resolve why your nitrates are climbing so much. SOMETHING is causing it. I would REALLY suggest an 90% water change, removing all those rocks for just long enough to make sure there isnt anything stuck under\between them. Dont clean your filter media so you keep your beneficial bacteria. You will need to float it while you clean if it will take a while, to make sure it doesnt dry out.
To help you resolve this, can you please give me a full breakdown of your setup? I really would like to know tank size, ammonia, nitrites and current nitrates. You seem to be getting the temp of his tank to drop, but what we want is something stable. Lets try getting him to around 16 degrees and getting it to stay there. As it gets colder, their metabolism slows, so perhaps not ideal since you dont feel it is impaction.
You said your fridge temp fluctuates...what are we talking here?