If it's the class name, then strictly speaking there should have been an actual first-vessel of the class named "USS Constitution II".
How do we know the USS Constitution wasn't refitted as well? Or perhaps it had been destroyed and not replaced? Or destroyed and eventually being replaced?
Publicity material (and a footnote in the novelization) mentions how Kirk was the first captain to return his ship at the end of his 5YM "relatively intact".
The concept of adding a letter to the registry number wasn't seen until ST IV. Before that, the only numbering precedent was the Galileo II replacing the Galileo shuttlecraft in TOS.