This is an accepted solution.
You'll likely need to do some coding for this one. Here's how I would approach:
1) Find the footer code (probably in theme.liquid or a snippet called something like footer.liquid).
2) Create a parent row container to encase the nav links and payment info.
3) Create child containers for each of those sections.
4) Using CSS, align/float the first container left and the 2nd container right.
5) Make mobile responsive by setting the container width of each to 100% at mobile sizes (will depend on your theme but you can check your existing CSS to see where the mobile breakpoints are).
*Do this on a backup theme in case anything goes wrong :)
If you're not comfortable working in code and need help, just give me a shout.
Sure, give me a shout at email@example.com and we can work out the details.