What was the evolutionary advantage of having seeds so large that they could only be dispersed by megafauna?
There are a few advantages to megafauna:

they travel large distances and are hence are likely to be able to
spread your seeds widely.
They also eat large amounts, so can carry a lot of seeds and
distribute those around widely.
Large fruit capable of being eaten only by the largest fauna might have the seeds survive by not being eaten and destroyed by smaller animals
Large animals have large guts, so the more of the seeds might survive undamaged

Another significant factor is that a megafauna animal also produces mega-feces, literally a large pile of nice warm fertilizer for the new plants to grow in.