SOPs for converting a digital circuit from 5V to 3.3V
It depends.  Simplest solution is to put in a 3.3V MCU and put bidirectional level shifters on all the signals.  If I2C is used, make sure the level shifter is I2C-safe (not all level shifters are bidirectional, not all are I2C-safe).  Make sure the 3.3V MCU comes on a board with its own 3.3V regulator, or you will have to add an external regulator to reduce the 5V to 3V.  With the level shifters, you don't have to care about the external 5V sensors or effectors; they will continue to run on 5V.  Look for level shifters at http://www.adafruit.com, for example.  If you have to replace the physical old MCU chip with a new chip, that's harder.  If I were doing it, I'd look at replacing the whole board with a new board.  If that wasn't feasible, I'd make a daughterboard with the new MCU, a 3.3V regulator, some voltage filtering capacitors, and the level shifters, and figure out how to place a socket on the old pins into which the daughterboard would plug.  This could be challenging if the old MCU used spacing other than 0.1" for its pins, in which case you would probably need a plug and matching socket with 0.05", or 0.66", or whatever spacing is used.

Oh, yes, and if the code is in assembler, you're screwed; if it is in C/C++, it is probably going to port, although I/O port numbers might have to change.  C/C++ with embedded low-level calls (register-tweaking) will be very painful to port.

Key question: why is it mandatory to change the MCU to 3.3V?  Most 5V chips are still available.  If the code is in C/C++ you could avoid the level shifter by selecting any 5V chip and reassigning output pins if necessary.  I presume you have the source code  If not, you have an impossible task.