Printing direct descendants of a category with WP_Query

From the Codex:

 child_of 
    (integer) Display all categories that are descendants (i.e. children & grandchildren) of the category identified by its ID. There is no default for this parameter. If the parameter is used, the hide_empty parameter is set to false. 

And…

parent  
    (integer) Display only categories that are direct descendants (i.e. children only) of the category identified by its ID. This does NOT work like the 'child_of' parameter. There is no default for this parameter. [In 2.8.4]

So, first, you are using the wrong argument if you only want the immediate decendants. You need:

$args = array('parent'   => $category_id);

Secondly, get_categories will give you an array of objects so you will need something like this to extract the IDs.

$cats = wp_list_pluck($categories,'cat_ID');
$args = array (
  'category__and'                    => $cats
);

Giving you:

$category_id = get_cat_ID('destinations');
$args = array('parent'   => $category_id);
$categories = get_categories($args);
$cats = wp_list_pluck($categories,'cat_ID');
$args = array (
  'category__and'                    => $cats
);
$recent_posts = new WP_Query($args);