Corp has two divisions - each has its own 401k plan. Plans each satisfy 410b and are tested separately.

Can one of the Plans go safe harbor without the other?

Yes, there's no problem with just one plan using the same harbor rules and not the other when the plans are not aggregated for 410(B) and other compliance tests.