Upgrading 2 breakers to AFCI, always trips
AFCIs are also a bit like GFCIs in that they care a lot about crossed neutrals.  A LOT.   You will never get any AFCI to hold while a crossed neutral persists, nor should you!  Remember, neutrals do not have breakers, the only thing that keeps them from overloading is the fact that they are fed from only one hot.  If they are fed by 3 hots, one could return 45A and of course start a fire in the walls.

You will have to identify every outlet (including hardwired ones) on each circuit.   Pull the covers off and the devices out.  Document how they are wired.   It is likely you will uncover the problem at that point. 

If not, disconnect them all and light up each circuit, one at a time, to determine which is the "first" outlet.  Hook up that outlet correctly (as opposed to  how it is now) and test.   Continue one at a time, thoroughly testing each time.   

When you run out of things to hook up, and you still don't have problems, then you have licked it.   Otherwise, the problem will return at a particular step. That is your problem area.

You seem sanguine about some crossed circuits in a 3-way light circuit.  That may be one of your problems, and there may not be a legit way to regain original functionality without going to smart switches.