Actually, the datasheet says the analog inputs are optimized for 10k or less so a 10k pot is probably the best choice.
I'm looking through the datasheet for the ATMEGA 328P, and wondering what page you found this information on. I found a bunch of tables listing the electrical characteristics (pg. 313 onward), but am having trouble finding the value you referenced.