Learn Russian: Он думает совсем иначе.

Yes! Он думает совсем по-другому means exactly the same thing. Иначе is a great word to know at this level. It means 'differently' or 'otherwise' and is just slightly more formal than по-другому, though both are very common in everyday speech.

I usually see совсем paired with не (like совсем не). What does it mean here on its own?

When used without не, the adverb совсем means 'completely', 'entirely', or 'quite'. So here, совсем иначе means 'completely differently' or 'quite differently'. When you add не, it flips the meaning to 'not at all'.

Where is the stress placed on the word иначе?

The standard stress falls on the second syllable: инАче. You might occasionally hear native speakers stress the first syllable in casual, fast speech, but инАче is the formally correct pronunciation.

Since our current lesson covers вместо (instead of), could I use it here to say he thinks 'instead of' the usual way?

Not quite! The preposition вместо is strictly used when one thing physically or conceptually replaces another. For example, Он думает вместо меня would mean 'He is doing the thinking instead of me' (he took over the task). To simply describe that his thoughts are different, you use an adverb like иначе, just as this sentence does.