WordPress Site Attacked by Spammers

Recently Google started listing my search engine results with a link saying, “This site may be compromised.”

I ensured my core was updated, plugins are all up-to-date, updating all my passwords. I found in my SEO Ultimate plugin that I was getting hundreds of 404 hits with super spammy URLs in the /wp-content and /images/icons folder.

Advice on next steps to find and fix this security concern? My site is losing serious traffic as a result.