Since they are both adjectives, is it possible to use them interchangeably on various occasions? When is the right time to use extraordinaire?
Generally, use extraordinaire if you want to put the adjective after the modified noun, want to make the noun sound more like a title, and want to add a touch of foreign flavor to the sentence. Use extraordinary if you want to put the adjective before the modified noun and communicate in an ordinary tone of voice.
Note that in a few cases, extraordinary also is used as an adjective after the noun. Example: Ambassador Extraordinary and Plenipotentiary
As already noted, in some contexts the two terms are interchangeable - apart from the fact that, being essentially just a co-opted French word, extraordinaire comes after the noun, not before.
But to me the most significant difference is that an xxxx extraordinaire is invariably "positive", and normally means an unusually fine example of xxxx. Whereas an extraordinary xxxx may simply mean an xxxx who happens to be unusual in some way - possibly in a negative sense, or unusual in some respect that doesn't directly relate to the fact of being an xxxx in the first place.
For example, whimsical/facetious usages aside, if you read of a saxophonist extraordinaire, you can be sure the writer believes his subject to be unusually talented - with the strong implication that many/most other fans of the instrument would agree with that assessment. But an extraordinary saxophonist might be unusual just because he has a non-standard playing technique. Or exhibits some bizarre quirk, such as always appearing on stage wearing a motor-cycle helmet.
Relating to that distinction, an extraordinary man wouldn't normally convey the same thing as a man extraordinaire. That second one is very much an extraordinary expression, and I can't even find any relevant written instances of an expression extraordinaire.