You will need to copy variable.php and create a coy in your theme.

Look for this on line 24

<option value=""><?php echo __( 'Choose an option', 'woocommerce' ) ?>&hellip;</option>

and replace it with

<option value=""><?php echo sprintf( __( 'Choose a %s', 'woocommerce' ), $woocommerce->attribute_label( $name ) ) ?>&hellip;</option>