I called a store to apologize for a actions that involved me. They told me that calling the store violates my ban and breaking their ban is against the law. They threatened to file a trespass complaint on me. Can they do so?
This depends on the nature of the "ban" ---i.e., who issued it, what legal power they have, and what it actually requires you to refrain from doing. You say it is "their ban" so I am going to assume that this is just a decision that the store has made not to allow you entry.
If it is indeed the store itself that has "banned" you, this would not prevent you from calling them to apologise for whatever you did. Calling a business on the phone cannot generally be considered a trespass --- at most, if you were to repeatedly call and harass a business over and over again, it might give rise to a nuisance suit. Unless you have extremely strange laws in your jurisdiction, it is almost certainly not against the law for you to call a business that has banned you, a fortiori if this phone call is made for the purposes of apologising for whatever you did that led to the ban.
Although it does not appear to be the situation in this case, if this ban was an actual restraining order of some kind issued by a Court, then it might indeed prevent you from contacting the business (in which case breaching it would lead to an action for contempt of court, not trespass). If a Court were to issue you with an injunction or restraining order of some kind to ban you from a business, then that instrument would specify what you are prevented from doing. You would then need to be very careful to comply with that order.
In short: there is a great deal of difference between a "ban" made by a store as the owner of property, and a ban issued by a court through an injunction or restraining order.
It's not against the law to call a store, but if they don't want you to call don't.