The consensus for earliest appearance of syphilis in Europe is at Naples in 1495, which would mean the pathogen was present in the Caribbean and traveled back with Columbus' first crew to Spain. The battle of Naples where it cropped up involved Spanish troops defending the Italian city against a French army filled out with an international panoply of mercenaries, hence the rapid spread across Europe.

Rothschild et al. (2000) has shown that skeletal remains in the Caribbean do exhibit signs of syphilis. As for the prevalence in the rest of the Americas, Baker & Armelagos (1988) is still the seminal paper on the American origin of syphilis. In it, they identify osteological changes indicative of treponomal disease in remains spread from the Eastern Woodlands, the Midwest, the Southwest, Mesoamerica, and Peru/Ecuador. While not all of the remains are clear cases of venereal syphilis, many do show distinctive remodeling that points away from skin infections. Given that the biological evidence is that treponomal skin infections have been with humanity since before we were Homo sapiens, it's safe to to say that a yaws-type infection was endemic throughout the Americas, and it was from this that syphilis evolved. Rothschild & Rothschild (2000) have gone so far as to posit this evolutionary change to have occurred in the Southwest about 2000 years ago.