2 wires with same neutral in a tandem circuit breaker on the same leg
You're correct, a multiwire branch circuit with a shared neutral is not safe with both hots on one tandem breaker, it requires a two pole breaker.  

If you move the hots for the MWBC to two adjacent tandems you will not be compliant with current codes but you'll avoid the main danger - you will no longer be overloading the neutral.  I'd address this immediately.  

That would have been compliant when this panel was new, and you'd be done, but current code requires that the switch on the breaker turn off both hots of the MWBC together.  This is to ensure that during maintenance both breakers are turned off and the MWBC is all the way dead, not half dead.  

You can comply with this requirement by using a two pole breaker or a listed handle tie to make sure the two adjacent breakers are turned off together.  A piece of wire through both handles may achieve the goal, but it is not listed.  I am not aware of a listed handle tie you can use here but I have never looked.  

To get a two pole breaker with the panel already crammed, you'd need to replace two adjacent tandems with a triplex breaker similar to what you have on the left side of your panel.  Those are 20's on the outsides with a two-pole 30 on the inside;  you'd need one with 20s on the outsides and a two-pole 20 for the MWBC on the inside.  

If all else fails you could install a small subpanel without too much expense to gain some space, and of course you could consider a panel upgrade which may be a good idea in the near future anyway.  

Again the main hazard here is the overloaded neutral, address that immediately, but you'll need to take care of the common switch for the MWBC to get fully compliant.