f^2 / fs describes the error range due to the discrete lags in correlation. It isn't the complete error model as there will be contributions from signal to noise (and interference such as non-harmonic content theorized as the issue above). I think a better approach to mitigating the discrete lag issue is interpolation as discussed earlier in the threat.
Aside from the discrete lag issue, the sample frequency needs only to be twice the highest frequency in the signal being digitized which can be controlled by a low pass filter prior to the ADC. Even high fidelity audio is typically only about 40 kHz sample rate. Autocorrelation works essentially by measuring the parts of the signal that match up cycle to cycle while rejecting parts of the signal that don't (random noise and non-harmonic cyclic content). The amount of rejection of the latter is proportional to the integration period so for this you want a longer sample. Given the limited memory for signal capture, this means there are conflicting requirements in that discrete lag error wants high fs and noise rejection wants a longer signal capture time. To optimize performance the best compromise between these needs to be determined.
With regard to your coding style, I like that you clearly broke the data capture and frequency determination into their own functions. This makes "loop" pretty obvious. In the readData function using "string" as a variable name is not descriptive of what it means and the very similar "String()" is a keyword. Both of these are bad practice. In a couple places you use "0.0000000625" which is the reciprocal of 16e6, the MCU master clock frequency. Using the latter would be more clear.