The simplest way is to place four "pointer" views above the map at each of the cardinal points. Then, as the user moves the map (using mapView:regionDidChangeAnimated: delegate method) determine which pointer should be shown. Hide all the other ones; and then show the correct one. Also, apply a transformation to the pointer so that the bearing angle is represented as you have done.
Here is a screenshot of a storyboard with the above configuration:

And here is a sample implementation (Code is not optimal, of course.):
//
//  MapViewController.m
//  AnimationTest
//
//  Created by Scott Atkinson on 4/17/15.
//
#import "MapViewController.h"
@import MapKit;
typedef NS_ENUM(NSInteger, CardinalPoint) {
    North,
    South,
    East,
    West
};
@interface MapViewController () <MKMapViewDelegate>
@property (weak, nonatomic) IBOutlet MKMapView *mapView;
// Views that show cardinal points on the map (Only one should be shown at a time)
@property (weak, nonatomic) IBOutlet UIView *northPointerView;
@property (weak, nonatomic) IBOutlet UIView *eastPointerView;
@property (weak, nonatomic) IBOutlet UIView *westPointerView;
@property (weak, nonatomic) IBOutlet UIView *southPointerView;
// Location to show on the map
@property (strong, nonatomic) CLLocation * targetLocation;
@end
@implementation MapViewController
- (void)viewDidLoad {
    [super viewDidLoad];
    [self hidePointerViews];
    // Add the location to the map
    self.targetLocation = [[CLLocation alloc] initWithLatitude:37.331898 longitude:-122.029824];
    MKPlacemark * placemark = [[MKPlacemark alloc] initWithCoordinate:self.targetLocation.coordinate addressDictionary:nil];
    [self.mapView addAnnotation:placemark];
}
// ******************** MKMapViewDelegate ********************
#pragma mark - MKMapViewDelegate
// As the map moves, update the cardinal pointer views
- (void) mapView:(MKMapView *)mapView regionDidChangeAnimated:(BOOL)animated {
    if([self isCurrentLocationVisible] && ![self isTargetLocationVisible]) {
        // The user location is visible, but the target is not, so show a pointer
        double bearing = [self bearingToLocation:self.targetLocation fromLocation:self.mapView.userLocation.location];
        [self showCardinalPointDirection:bearing];
    } else {
        // Hide the pointers
        [self hidePointerViews];
    }
}
// ******************** Coordinate Helpers ********************
#pragma mark - Coordinate Helpers
- (BOOL) isCurrentLocationVisible {
    return MKMapRectContainsPoint(self.mapView.visibleMapRect,
                                  MKMapPointForCoordinate(self.mapView.userLocation.coordinate));
}
- (BOOL) isTargetLocationVisible {
    return MKMapRectContainsPoint(self.mapView.visibleMapRect,
                                  MKMapPointForCoordinate(self.targetLocation.coordinate));
}
// From: http://stackoverflow.com/questions/3925942/cllocation-category-for-calculating-bearing-w-haversine-function
double DegreesToRadians(double degrees) {return degrees * M_PI / 180.0;};
double RadiansToDegrees(double radians) {return radians * 180.0/M_PI;};
/// Calculate the bearing between two points
-(double) bearingToLocation:(CLLocation *) destinationLocation fromLocation:(CLLocation *) fromLocation {
    double lat1 = DegreesToRadians(fromLocation.coordinate.latitude);
    double lon1 = DegreesToRadians(fromLocation.coordinate.longitude);
    double lat2 = DegreesToRadians(destinationLocation.coordinate.latitude);
    double lon2 = DegreesToRadians(destinationLocation.coordinate.longitude);
    double dLon = lon2 - lon1;
    double y = sin(dLon) * cos(lat2);
    double x = cos(lat1) * sin(lat2) - sin(lat1) * cos(lat2) * cos(dLon);
    double radiansBearing = atan2(y, x);
    if(radiansBearing < 0.0)
        radiansBearing += 2*M_PI;
    return RadiansToDegrees(radiansBearing);
}
// ******************** Pointer View ********************
#pragma mark - Pointer View
- (void) hidePointerViews {
    self.northPointerView.hidden =
    self.southPointerView.hidden =
    self.eastPointerView.hidden =
    self.westPointerView.hidden = YES;
}
- (void) showCardinalPointDirection:(double) bearing {
    CardinalPoint point = [self cardinalPointWithBearing:bearing];
    // Determine which pointer should be shown based on the bearing
    UIView * activePointer;
    switch (point) {
        case North:
            activePointer = self.northPointerView;
            break;
        case South:
            activePointer = self.southPointerView;
            break;
        case East:
            activePointer = self.eastPointerView;
            break;
        case West:
            activePointer = self.westPointerView;
            break;
    }
    // Rotate the pointer to show the bearing
    activePointer.transform = CGAffineTransformMakeRotation(DegreesToRadians(bearing));
    // Hide all pointers except the pertinent one
    [self hidePointerViews];
    activePointer.hidden = NO;
}
/// Returns the cardinal point for a given bearing (in Degrees)
- (CardinalPoint) cardinalPointWithBearing:(double) bearing {
    if (bearing > 45.0 && bearing <= 135.0) {
        return East;
    } else if (bearing > 135.0 && bearing <= 225.0) {
        return South;
    } else if (bearing > 225.0 && bearing <= 315.0) {
        return West;
    } else {
        return North;
    }
}
@end
Additionally, the pointer rotation is based on the bearing between the userLocation and the targetLocation. It feels a little strange. Probably better to make the rotation based off of some other point. Maybe the center of the visible region at that moment...