I'm pretty sure this is a bug? Game #124944197
I have Innovation and one Favor token. I play a Replace, which gains a Sycophant. There should be two on-gain triggers for Sycophant: get two favors, play it with Innovation -- I am not presented with a choice, but instead I am given the two favors after I'm done playing the Sycophant, which is after the trigger for Circle of Witches, so I can't give out a Curse now.
I couldn't find anything in any FAQ or rules docs about this, but I thought the timing of Innovation and Sycophant's on-gain effects would be the same (when I gained the Sycophant) so I should get the choice to get the Favors first.
You are right, you should have been given the option to get the Favors first.
That's what happens on a reload for me:
(https://i.imgur.com/POeugYH.png)
I could choose the Sycophant option first, resulting in being able to activate the Circle of Witches. But in the real game the "Sycophant" button might have been missing (for unknown reasons), resulting in the bad outcome you described.