Can you try something for me. So just saying this for my own self but a Flow action can either be linked to a Connection or a connection reference.
I find that many times if I accidentally "think" I deleted a connection but I still had references it can cause issues.
1) you can do one more check and its just for... sanity
Go to Solutions
open Default Solution
look at connections and make sure you see nothing
2) I promise, there is a SQL action that thinks its still there. you have to make sure be suuuupppeerrr careful that you open every single action. I miss them all the time no matter what I think
3) Go through and in the first action create a New connection. Then save and close the flow
4) go back to your solution and create a new Connection reference pointing to the connection you created from that action(not outside of it).
5) save and publish
6) go back to your flow and now re-establish them all to use the new connection reference.
You have to make sure you are not just publishing your app, but (and don't do t his from the Solution, regardless of what it says), go to the Solutions tab, select nothing select Publish all Customizations.
If you didnt do this before, thats the issue.
If you did, try following my steps and doing it again.
Come back if it doesn't work. I promise its there somewhere.. even if you dont see it and it could just be metadata stuck hence the steps I am asking you to do