Ok here is the solution I found:
You are not meant to set IDs when creating new objects like categories. Instead I created the parent categories first using something like
$my_cat = array(
'cat_name' => 'Community News & Views',
'category_nicename' => 'news',
'taxonomy' => 'category'
);
$my_cat_id = wp_insert_category($my_cat);
In a second step I create the child categories using
$parent_term = term_exists( 'news', 'category' );
$parent_term_id = $parent_term['term_id'];
$my_cat = array(
'cat_name' => 'Business Articles',
'category_nicename' => 'business-articles',
'category_parent' => $parent_term_id,
'taxonomy' => 'category'
);
$my_cat_id = wp_insert_category($my_cat);
Note: You cannot create Parent and Child categories at the same time because the parent category has to exist, when you create the Child category
Note also: term_exists( 'news', 'category' );
uses the $slug as first argument. The codex is not so clear on that one.