Why is EDTA most soluble at a pH 8? (addition of NaOH)
A disodium salt of EDTA also has two remaining carboxylic-acid groups, which can be deprotonated by addition of base, like $\ce{NaOH}$. By the way, higher pH is generally better especially if you plan to use it for chelation, i.e. cation-capture. The labs I've taught in the past use buffers of pH ~10 with EDTA for complexometric titration experiments.

Deprotonating an organic acid in general improves solubility in water because the electrostatic interactions of $\ce{-O^-}$ and the solvent (the hydrogens on water) are stronger than interactions of $\ce{-OH^0}$ and water.

A similar example would be 4-t-butylphenol, which is nearly impossible to dissolve in water without addition of a base, e.g. $\ce{NaOH}$. In experiments I had to reach pH of about 12 to strip the compound of the alcohol-proton, yielding a negative charge which interacts more strongly with water.

Nonetheless you can still make a decently concentrated (~0.1M) solution of EDTA in water by stirring alone, if you allow a stir-plate to do the work for ~30 minutes.

In short, it's not the addition of $\ce{Na+}$ that matters, but rather the addition of $\ce{OH-}$, to increase solubility.