Factor Xa is, in theory, highly specific. Would your protein be inherently unstable? Do you see those nonspecific bands if you leave your sample without factor Xa?
If you don't want to use factor Xa, the most straight forward approach is to reclone it in another vector with a different cleavage site. NEB used to sell pMAL-c5E, which replaces the factor Xa cleavage site with an enterokinase one, but it's now been discontinued (see link). Or you can insert an extra cleavage site between the factor Xa site and your target protein.
What do you mean by "non specific"? Is it rather "unanticipated"? Do youactually generate free MBP during digest?
Factor Xa being highly specific, I guess you get unexpected digest profile which may be due to the presence of cleavage site(s) within the sequence of your protein of interest.
Proteases can certainly cut non-specifically. I've had several tagged proteins that have no predicted sites for that specific protease in them (other than at the junction), yet have been cut to pieces when trying to remove a tag. I don't often use Xa, but thrombin can certainly do this.
In my experience, this often means that the protein of interest, although it may have been solubilized by the tag, has not actually folded correctly. [Note - I am assuming you have the MBP on there as the protein is insoluble with just a His-Tag. If you haven't tried that yet, then do it.]
Other times, the specific cleavage site appears blocked in some way by the folding of the fusion and extremely high levels of protease are needed, which can lead to non-specific digestion.
Have you titrated the protease to ensure you are not adding too much?
My next suggestion is to try re-cloning with a different protease site (TEV is always one of my favourites) and, if that doesn't work, reclone with a different solubility tag (and a TEV cleavage site).