Do as many water changes as you need to, and as large as you need to until the NO3 is very low. Then monitor it to see how fast it rises.
From what you are describing the only source of NO3 is shrimp food (Protein ends up as NO3), and that is fed sparingly. So the NO3 should not rise very fast.
If it does, then there is some other source of nitrogen that is getting turned into nitrate.
How about improving conditions for the plants so they remove more N?
Light, CO2, other nutrients besides N.