Ok, now this is something that has never made sense to me, the idea of bioballs increasing nitrate levels.
Nitrate is the necessary end of the oxidation/conversion process of ammonia (nitrogenous waste). If you have ammonia, and you will, it must be converted. The natural process first creates nitrite, then nitrate. It doesn't matter on what medium this is done, it must be accomplished.
How would the medium itself contribute to an increase the nitrate when you're working with a given quantity of ammonia to start? It can't. What you need is either to reduce the amount of ammonia (nitrogenous wastes) available for conversion in the first place OR denitrification (via those nifty little anaerobic bacteria that exist deep within live rock). Better yet, in my opinion, have available in the system those organisms that utilize unconverted ammonia/nitrogenous waste directly. The issue I have with something like bioballs is that they don't have a surface that keeps the beneficial benthics safe from being accidentally washed off. They also don't have "deep tissues" where denitrifyers can live.
In my opinion a 40gal. is small for a BTA.
As for the last question regarding the "addition" of beneficial bacteria, you must remember that in order for them to exist there must be sufficient food. In other words there will only be as much bacteria available to perform conversion as there is waste available for them to convert. Change that balance, or do something that harm these (benthic) bacteria, and you will see a change in your readings.
You did change the bioload with the addition of the blenny and anemone, and something that seems small to you is big in a system as small as 40 gallons. Also, if the LR was ever moved out of the water you simply must expect that some organisms were damaged such that they ultimately did not survive.
So, how far off are the readings? How long have you been maintaining a presumed zero level of nitrate? Are you certain of your test's reliability? And have you changed anything else?
Do the water changes I suggested, test immediately afterwards. Then give it some time, test again and see what happens. If the nitrate went down after the water change, then came back up, your live rock isn't performing the denitrification that one would hope for. Converting the sump to a 'fuge and adding macroalgae that will consume wastes before conversion will do a great deal to eliminate this problem, should it prove to be one.