Sigh, I should have seen this coming after that Female knighthood question....

u/MoiMagnus has explained the etymology, and the Latin senior was a common deferential title used for knights and lords into the 12th and 13th centuries. The first time the English derived words show up (according to the OED at least) are in the last quarter of the 13th century - a reference to "sire Arthur" in a c. 1275 Brut (Arthurian prose) and a "sir Hubert de boru" in Robert of Gloucester's Chronicle for the year 1297.

Interestingly, for the George Martin fans from the other thread, it appears that 'ser' and 'sere' were actually quite familiar spellings/pronunciations in Middle English, although not as common 'sir'; the first known reference if from the c.1300 religious poem Cursor Mundi refering to a 'sere biscop' (sir bishop/my lord bishop).