How do I get the parent category if I know the child category?

get_category_parents() requires the category ID to be passed as the first parameter, and returns an array a string of all the parents, separated by / by default. You can change this to a space to include them in your class list:

foreach ( $categories as $category ) {
    // Get the parents, separated by a space
    $parents = get_category_parents( $category->id, false, ' ' );

    // If $parents isn't an error, carry on
    if ( ! is_a( $parents, 'WP_Error' ) ) {
        $menu .= '<option class="' . $parents . '" value="' . $category->name . '">' . $category->name . '</option>';
    }
}

If you want to get all sorts of kooky, you can also print out your HTML like thus:

$menu .= sprintf( "<option class="%s" value="%s">%s</option>",
                  esc_attr( $parents ),
                  esc_attr( $category->name ),
                  esc_attr__( $category->name )
         );