AVR Freaks

What kind of signal feeds the non inverting input of the operational amplifier ?
Frequency, Vlow, Vhigh, almost sinewave, perfect squarewave ?

According to the most datasheets, LM358 has an open loop gain of over 100dB in DC, but only 50dB at 2kHz. That makes a gain of 300 without any negative loop, so you external resistor divider trying to set the gain to 10,000 is useless, because the opamp acts as an open loop one at that frequency. That makes it very unstable, maybe even self oscillating at any random stimulus and susceptible to noise.

My decision would be to use the entire LM358 package (if must be this one) as follows:

first stage opamp as a 3kHz low pass filter with DC gain set to 50, followed by the second stage acting as a hysteresis comparator (0.15V, +/- 50mV) for covering the entire input range 5-100mVpp. The comparator's output has to be tied to V+ by a 1-10K resistor because LM358 will output only 3.5V as John already told you.

Depending by your signal source i would also consider AC coupled input.
The voltage supply must be separated by the digital circuit by an RC or LC filter, decoupling must be well done and analog ground tied in only one point to the digital ground.

I doubt, 3 people told you about noise and too much gain.

Most likely is to be no change and if it is, the circuit will be unreliable IMO. You already had that gain of 300 (50dB) at 2kHz however you set it equal 300, 1000, or 10,000.
Check the datasheet, the open loop gain of LM358 at 2kHz is 50dB = 300. You can't make it higher whatever resistors you put or not.
Trying to set it to 10,000 or 300, or just not adding any resistor will keep gain to 300. However you set it as 300, it will behave as an open loop opamp with all its troubles at that frequency.

All you can do is to lower it. If you want those simple relations between resistors and gain to be almost true, and thus have a predictable circuit, you have to accept only 1/10 of open loop gain as your maximum gain. That makes 30 at 2kHz and I suggested 50.

If a different type of AVR lives with your circuit fine, the problem is somewhere in the configuration of your pins, potentially affected by something you hide behind the "...." in your conditional statement. Unfortunately, this means that the datasheet has to be studied carefully many times: Atmel doesn't like to mention same thing twice.

If the PINF[1] has clear logic levels of random 0 and 1 on scope, my opinion is they are set this way by the op-amp. It's not about PINF[1] becoming output from time to time and shorting two outputs.
My bet would be that different instructions generate different supply currents which triggers false flip-flops in the op-amp especially when the input signal is in the mid-range. That is why i would use a comparator with hysteresis.

However, is worth checking if these problems still appears when the analog input is at steady 0V and 5mV.
Would be also good to temporary put a 10K resistor between analog input and ground and see if it helps.

What about not directly connecting the op-amp output to the uC, but using a 1-10K resistor ? Would be interesting if the evil stays alive.