Can I associate a custom post type with another custom post type?

Yes, you can.

You would need to add a custom field that would store the ID of other post type. I would recommend using a select list.

You could try something along these lines:

add_action( 'add_meta_boxes', 'wpse_143600_add_box' );
add_action( 'save_post', '143600_save_box' );

//create the metabox
function wpse_143600_add_box() {
   add_meta_box( 
    'related_testimonial',
    __( 'Testimonails', 'wpse_143600_translation' ),
    'wpse_143600_testimonial_box',
    'locations',
    'normal'
    );
}

//build the box
function wpse_143600_testimonial_box($post) {

wp_nonce_field( basename( __FILE__ ), 'wpse_143600_nonce' );

$wpse_143600_stored_meta = get_post_meta( $post->ID );

$testimonialArgs = array(
'post_type' => 'testimonials',
'post_status' => 'publish',
'numberposts' => -1
);

$testimonials = get_posts($testimonialArgs);

if($testimonials): ?>
<p>
  <label for="meta-select" class="wpse_143600-row-title"><?php _e( 'Example Select Input', 'wpse_143600_translation' )?></label>
  <select name="meta-select" id="meta-select">
    <option value="NULL">Please choose a testimonial…</option>
<?php foreach($testimonials as $testimonial): ?>
    <option value="<?php echo $testimonial->ID; ?>" <?php if ( isset ( $wpse_143600_stored_meta['meta-select'] ) ) selected( $wpse_143600_stored_meta['meta-select'][0], $testimonial->ID ); ?>><?php echo $testimonial->post_title; ?></option>
<?php endforeach; ?>
  </select>
</p>    
<?php
else:
?>
<p>There are no testimonials - please save this post, and write some testimonials. You'll then be able to choose a testimonial for this location.</p>
<?php
endif;
}

//save the box
function wpse_143600_save_box( $post_id ) {
$is_autosave = wp_is_post_autosave( $post_id );
$is_revision = wp_is_post_revision( $post_id );
$is_valid_nonce = ( isset( $_POST[ 'wpse_143600_nonce' ] ) && wp_verify_nonce( $_POST[ 'wpse_143600_nonce' ], basename( __FILE__ ) ) ) ? 'true' : 'false';

// Exits script depending on save status
if ( $is_autosave || $is_revision || !$is_valid_nonce ) {
    return;
}
// Checks for input and saves if needed
if( isset( $_POST[ 'meta-select' ] ) ) {
update_post_meta( $post_id, 'meta-select', $_POST[ 'meta-select' ] );
}
}

That’s fairly rough code, but should get you close.

Sorry about the length, you can find it on pastebin: http://pastebin.com/zA4aDiV9