/bin/sh^M: bad interpreter: No such file or directory

This worked for me:

Open file /usr/local/bin/brew with vi (vi /usr/local/bin/brew)
While on vi issue this commad (via esc or :) :set fileformat=unix
Close file on vi via :wq!
The brew command should be OK now.

Regards.