"We'll reveal incriminating information to the police unless you pay us $500 and perform this service," is pretty textbook blackmail. The law often doesn't make any distinction about the type of action because it relies on prosecutorial discretion for that.
The problem is that they aren't involving the courts. Specifically, there's no trial or court proceedings to determine the facts of the case or to ensure that the offender's rights are being protected. The offender doesn't get the right to an attorney. They aren't guaranteed to know all the evidence against themselves. There's no way to know that a given Walmart store isn't blackmailing it's customers.
If Walmart started a nationwide program which provided these services to any shoplifter as an alternative program that a judge could sentence the offender to or that a prosecutor could recommend, it would be perfectly fine and may have the same effect in reducing recidivism for shoplifting at Walmart and other stores. The problem is that it's all taking place behind closed doors, so there's no way to know that it's not blackmail. It's not even necessarily in the best interest of the general pubic. It means that people who shoplift aren't being tracked, meaning when they do re-offend and get caught they appear to be first time offenders to the state.
Furthermore, there's no way to know what criteria Walmart is using for this program. Even ignoring the fact that at $500 it's a get-out-of-jail-free card is only for middle class and upper class individuals, what if Walmart only offers the program to whites or women but always prosecutes blacks, Hispanics, and homosexuals?
In reality, if we want first time offenders to get lesser charges or face lesser punishment, then we need to change the actual law and reduce the actual punishment for the crime. If the law is unfair, the answer is to change the law, not to find ways around it. This is the exact same reason the police argument against body cameras -- lack of police discretion -- is bullshit. If the laws are unjust or don't best serve the public, the answer isn't to allow uneven enforcement. That just leads to abuse!