原因が完全に判ったわけではありませんが...

まず，shebang 行(スクリプトの1行目)で存在しないファイルをインタープリタに指定した場合のメッセージは #1 とは異なります．

$ cat xxx.sh 
#!/bin/bas
echo Hello
$ ./xxx.sh
bash: ./xxx.sh: /bin/bas: bad interpreter: No such file or directory

#1 と同じメッセージはコメント文字 # をバックスラッシュでエスケープすると再現できます．
(この場合 #! はカレントディレクトリに存在するはずのディレクトリとみなされています）

$ cat xxx.sh
\#!/bin/bash
echo Hello
$ bash xxx.sh
xxx.sh: line 1: #!/bin/bash: No such file or directory
Hello

ですから問題のメッセージは，
「#!/bin/bash が #! も含めて実行ファイルへのパスと解釈されて実行されようとしたが見つからなかった．」
と読み取れます．

また，# の前にスペース以外の非表示文字が混入した場合も (例ではバックスペース = ASCII コード 8)

$ head -1 xxx.sh | od -c
0000000  \b   #   !   /   b   i   n   /   b   a   s   h  \n
0000015
$ cat xxx.sh
#!/bin/bash
echo Hello
$ bash xxx.sh 
xxx.sh: line 1:#!/bin/bash: No such file or directory
Hello

となります．(ただし，メッセージで # の前のスペースがなくなっています)

ともかく，問題のメッセージからは shebang行 に問題が有るように思えます．
とりあえず file コマンドで件の xxx.sh を調べてください．shebang行 が不正な場合 file コマンドは

$ file xxx.sh
xxx.sh: Bourne-Again shell script text executable

以外の結果 -- 例えば ASCII Text -- を返します．

なにで編集しましたか？
Windows環境で編集しましたか？
BOMが付いているのが問題なので、削れば直ります。

無事解決しました。ありがとうございました。

Windows環境で編集したときに、BOMが付いてしまったようです。
vi で以下のコマンドで BOM を取り除いたところ、件のメッセージは表示されなくなりました。

:set nobomb

別のサーバーでは、Windows環境で編集したものを使用してなかったため、
BOM が付かずに、件のメッセージが表示されなかったのだと思います。

この度は、本当に勉強になりました。ありがとうございました。