Right… The cap needs to filter the signal at the Arduino input. 
How much noise are you getting? Is the noise worse with the pot at maximum, or in the middle? I assume the noise is OK at low settings?
MIDI CC is 8-bits, right? You should be able to get a “stable” reading at 8-bits. But, with ANY analog-to-digital conversion you can be on the “hairy edge” and the reading can jump up-and-down by one count. If that’s a problem, you have to deal with it in software (and there a couple of ways to do that, depending on your requirements).
Higher value pots are more susceptible to electromagnetic noise pickup. i.e. 100K is probably too high, but it depends on the “electrical environment”.
Longer wire-runs are more susceptible to noise pickup.
Higher value capacitors will give you more filtering. If the capacitor is too large you’ll filter (slow-down) the pot-adjustments and your adjustments will be delayed. But, that shouldn’t be a problem with 100uF or less.
A higher value pot will also give you more filtering with a given capacitor, but since the noise pick-up is worse with higher resistance, it’s usually best to use a lower value pot and a bigger capacitor.
If you get noise with the pot a maximum (5V out) you are getting noise from the power supply. (And, that might take a BIG capacitor, or a different power supply. (With the pot at maximum, you’ve got the capacitor across the 5V supply, effectively the same as your schematic shows now.)
You can also filter in software (i.e. average the readings), but you may not want to take-away processing power from whatever else your code is doing. (I’d start with a capacitor filter.)
All caps we’ve tried so far have been 63 volts.
That’s not important. The voltage rating on a capacitor is the maximum you can safely apply. You’ve only got 5V and I’ve never seen a capacitor that can’t handle 5V. (They may exist, but I’ve never seen one.)