This is check fraud, be careful, and don't run back to the bank without planning (but plan fast)
That is likely not as bad as it sounds. People occasionally bounce checks (also check fraud), and a single slip-up will likely be forgiven if you are proactive.
Before going to the bank and explaining the situation
Make sure you actually did mobile deposit the check (1st time) then re-deposit it in person (2nd time). Most banks will have check photos available online. Print this out and bring it to the bank. They should have an image of the 2nd deposit on file. Don't go to the bank without the image of the first check. Banks are required to maintain records for 5 years
Don't go to the bank without a check or a repayment plan
If you can just withdraw the extra money and write a check back to the bank that's the best plan. It's unlikely any bank would do anything but take the money back. Remember to get the amount in writing from the first bank and take a photo of the check before you deposit it back. If you cannot do this, go in with a repayment plan.
Keep all the records on file. If there is an issue after-the-fact, you want to be in a position to prove you fixed the mistake.
NOTE: Check was cashed at a "Check-2-Cash" place, not a bank
This will not work in your favor. These places are shady, which makes it look more like an intentional deception on your part. You still need to go in with a plan (see above), but this means you should move twice as fast to make sure this gets resolved.
And whatever you do, DON'T USE ANY PLACE WITH A NEON SIGN TO CASH A CHECK! Use a bank!