Display custom post types in dropdown with option “all”

Add an empty option in first position:

...
echo '<option value="">All locations</option>';
$query = new WP_Query( $args );
while ( $query->have_posts() ) : $query->the_post();
    echo '<option value="' . get_the_ID() . '">' . get_the_title() . '</option>';
endwhile;
...