Since im here im going to respond to this with a couple of things.

"While Cloudflare offers many optimization services and DDoS protection, many of them break Magento and Wordpress functionality."

I've not had any issue with this. Typically if something does break in WP or Magneto its pretty simple to fix. Personally, i dont run WP sites without cloudflare, its too much of a security issue.

" Implementing caching and Google PageSpeed with Nginx or Apache shows much better performance,"

You should do this anyway....

" Worse though, Cloudflare doesn't allow you to use your own SSL on any plan under $200/moth"

Sure it does, i run 40 + sites on standard Comodo SSL certs on Cloudflare pro without issue.

"If you're a Pagespeed/YSlow nut, they you'll really be upset to learn Cloudflare adds a security cookie to everything, so there is no way to have serve content on a cookie-free domain when using Cloudflare DNS"

Thats a fair point, though perhaps not such an issue in most situations.

"Customer service is also slow and mostly automated, so don't expect great service on unpaid plans."

Again i dont really find this. Most of my accounts are CF Pro but for those that arn't, i dont notice any difference in support level. I know Business and Enterprise plans get faster support but for $200 + a month, i'd expect that anyway.

You may find that you have to wrap the code that gets called when Ajax fires in something to catch the user agent. I.e. if your making an Ajax request to a php script in order to return data, you could wrap that php code in something like this (please excuse the Sudo code):

if(in_array($_SERVER['HTTP_USER_AGENT'], $knownagents){

//known webspider, or blocked agent, return nothing.

return "";

} else {

//not a known spider so continue.

}

?>

Thats very generalised but you get the idea. I put a short list together in JSON format a while back, you can find it here if its of any use: https://www.source-control.co.uk/knownspiders/spiders.php

PM me if you need any more specific help than that with development, hopefully someone else will have a slightly easier way of dealing with this though heh

Thats a good point actually, being UK based, i tend to forget States in the US is how you're likely to do location redirects (that and i read Colorado as Canada... my bad).

The short answer i think is not directly. You could use the users IP address and something called mode_geoip in order to handle the redirects, it takes a bit more configuration and setup though.

Im seeing lots about redirecting on country, not all that much on redirecting on state, but a good starting point is perhaps this Stackoverflow thread. It's probably something you'll need to ask a developer to do.

http://stackoverflow.com/questions/9838344/how-to-redirect-domain-according-to-country-ip-address

There are a number of solutions, perhaps the easiest and best solution is to add Cloudflare to your site, and take a look at this blog:

http://netjunky.net/redirect-web-traffic-based-on-country-origin/

(this assumes your website runs on PHP)

Looks like you've been hacked then,

You'll need to clean out your code and content and make sure wordpress and all of its plugins are the latest version. Unfortunatly there is no 'Safe' way to recover from this without reverting to a backup from before the hack.

https://codex.wordpress.org/FAQ_My_site_was_hacked

EDIT::
I deleted my other response because i fail at reading :P, sorry about that

What Patrick Delehanty has said is completely correct. You need to edit your pages, menu's etc in order to remove or fix the links that have 404's if they are part of your website.

If the links are external websites linking to you, you need to setup redirects in your .htaccess file for them. The later is considerably more technical so if your not confident with it, ask your developer to do it for you.

If your not sure which it is, could you provide is with an example of a link that shows as a 404?

You can also use Xenu to check the links on your site (not the ones linking to it), i find it works better than the Broken Link Checker plugin.

Got to love that referal spam!

I've not seen this one yet in my reports, kind of disappointing really :(.

As has been suggested you can request the removal of pages in GWMT and you should keep any wordpress site and plugins up to date.

To add to this, you might want to look at something like Cloudflare as an extra layer to protect your clients site. We've been using it for a year now and its made a massive difference, both to performance and security.