replaceOccurrencesOfString:... will traverse the string each time you call it.
An alternative which should make the replacement faster is to manually traverse the string just once and build a new string along the way.
Here's an example, although there's probably still room for further optimization
- (NSString *)encodeEntity:(NSString *)string {
    NSUInteger length = string.length;
    NSMutableString *encodedString = [NSMutableString stringWithCapacity:length];
    unichar buffer[length + 1];
    [string getCharacters:buffer range:(NSRange){0, length}];
    for(NSUInteger i = 0; i < length; i++) {
        char current = buffer[i];
        switch(current) {
            case '&':  [encodedString appendString:@"&"];        break;
            case '\"': [encodedString appendString:@"""];       break;
            case '\'': [encodedString appendString:@"'"];       break;
            case '<':  [encodedString appendString:@"<"];         break;
            case '>':  [encodedString appendString:@">"];         break;
            default:   [encodedString appendFormat:@"%c", current];  break;
        }
    }
    return encodedString;
}
Also if your specific issue is to escape XML entities, this question may be useful: Objective C HTML escape/unescape