OK, this helped to solve this issue. What I ended up with is:
$new_cat_id = wp_insert_category($new_cat);
$values['choices'] = 'product';
update_field('field_54d4c68c4aa5e',$values, 'product_cat_'.$new_cat_id);
Thanks for pointing me in the right direction.