The store locator』s first field, by default, is labelled with: Enter your postal code, city and / or state
As of version 7.5 of Yoast SEO: Local, this label can be customized using the developer filter: yoast-local-seo-search-label.
add_filter( 'yoast-local-seo-search-label', function( $search_label ) {
$search_label = 'Your new search label';
return $search_label;
} );