I understand that DMCA complaints only work for search engines and webhosts which are based in the US.
However, does the person filing the complaint also have to be in the US, or can anyone in any country file a complaint to a US host?
The DMCA is U.S. law, however, many organizations and search engines participate in a sort of co-operative organization to satisfy these requests. If you file the DMCA complaint through Google, they inform Chilling Effects which is the de-facto organization which in turn will act as the information clearing house for anyone else who participates in removing copyrighted material. Your site does not have to be a U.S. site for this.
It certainly does not hurt to make this your first step. It may take a few days for everyone who is cooperating to see your complaint and act upon it. From there, you may have to take other steps for specific sites on a case by case basis. Just filing the complaint may be enough.