I did the $line =~ s/\xef\xbb\xbf// and it didn't remove the characters!

Using the advice from kcott here to use /g, it works for me. If it really doesn't work for you, then perhaps the data you have in your Perl string is not what you think it is. See my node here for advice on how to show us the real data, in particular Devel::Peek, and make sure to provide an SSCCE that we can run to see the problem for ourselves.