Vincent's limit is 65535 kills, but you do not need that many kills to reach a damage overflow. Using stuff like Berserk, Hero Drinks and Critical Hits, you can easily reach an overflow much earlier. Oh and I heard it's not possible to get an overflow against Ruby Weapon because of its high defense. (Emerald has only 80)

On topic, I think it's easiest to put mastered W-materia, Hades and KotR into Barret's weapon, his damage increases pretty fast and you can hit for 9999 with Morph relatively easy.