Yes, it's definitely inefficient -- think of all the realloc()ing and memory moving that needs to be done on each -replaceCharacters call if it's a big string.
Typically it's better to build up a new NSMutableString, searching through the first string iteratvely, and adding the necessary substrings to the new NSMutableString. I.e, whenever you find a match, add the substring since the last match then add the replacement string, wash, rinse, repeat. You can use -rangeOfString:options:range: to limit the range of the search to just the areas you haven't searched yet.
However, for the simple substitution you're doing, there's a much easier way:
newString = [[testString componentsSeparatedByString:@"\n"] componentsJoinedByString:@"<br>"];
[If you must modify the testString instance in place, then just add [testString setString:newString] afterwards.]
BTW, you might want to replace with @"<br>\n" so the resulting text is somewhat readable, but that's up to you :-)