Let's assume it was Google that did this, and let's assume that it was non-authorised behaviour by a branch office. (I hope for their sake this isn't the case, but there is more than enough evidence to make it possible)

What should Google do?

Obviously they shouldn't dodge the responsibility, but also they should try and repair the damage somehow.

What is an appropriate course of action for them? Paying damages? Transferring customers?

I can't think of any good options, really.