Searching user meta using WP_User_Query

Try this:

$yoursearchquery = 'This is my search';
$users = new WP_User_Query(array(
    'search' => $yoursearchquery,
    'meta_query' => array(
        'relation' => 'OR',
        array(
            'key' => 'shoe_size',
            'value' => $yoursearchquery,
            'compare' => 'LIKE'
        ),
        array(
            'key' => 'shoe_color',
            'value' => $search_operation,
            'compare' => 'LIKE'
        ),
        array(
            'key' => 'shoe_maker',
            'value' => $yoursearchquery,
            'compare' => '='
        )
    )
));