The story
From carotid + -dynia via erroneous rebracketing of -odynia; in other words, whereas the suffix -dynia is morphologically appropriate in words such as aquadynia and dermatodynia, its use in the coining of the word carotidynia was a misapprehension that got propagated into widespread use and is now idiomatically established, notwithstanding the objection.
Etymology from Wiktionary, CC BY-SA 4.0.