So, it's easy. ADC is measuring the ratio between its reference and the signal. When you have just the pot, the noise from the power line is in both signal and reference, so it is effectively cancelled out. But when you connect a cap across a pot, you filter away the noise from your signal while still having the noise in reference, so you get noisy results.
Try changing the reference to internal bandgap one. Or power your arduino from a low-noise external power supply (usb port of a computer isn't low noise).