From Wikipedia: "In classical Greek, as in classical Latin, only upper-case letters existed. The lower-case Greek letters were developed much later by medieval scribes to permit a faster, more convenient cursive writing style with the use of ink and quill."
On the other hand (Wikipedia again) "the oldest surviving Latin translation of the Elements is a 12th century work by Adelard, which translates to Latin from the Arabic."
In other words, there is no clear connection between Euclid using uppercase (the only script he knew), and us using it too (what symbols did the old arab scholars use?). There is no point either in looking at "old" books like Coxeter's. The convention is surely older!
I will hazard the guess that the convention is quite old, say 1700-1800, and that it started with some random edition of Euclid that became slightly more popular than others. Which one, I do not know, but it is improbable that it is the first English translation by Billingsley (very famous, with 3D pop-out models of solids, but English was not the most influential language at the time), or Oliver Byrne's [color coded edition](http://en.wikipedia.org/wiki/Oliver_Byrne_(mathematician\)#Byrne.27s_Euclidhttp://en.wikipedia.org/wiki/Oliver\_Byrne\_(mathematician\)\#Byrne.27s\_Euclid) (which is beautiful, but became well known only recently, AND does not use labels :). See also this page...
BTW, in Spanish points are also represented with capital letters.