You can take the relevant parts of the header navigation code from /includes/templates/your_template/common/tpl_header.php and add them elsewhere. (I added them to column_left.php.) In this case, /includes/templates/your_template/sideboxes/tpl_categories.php would probably work.
At the top of the file, find
Depending on what you want, you should be able to add the nav code to $content either before or just after the content div opens. You may need to massage the presentation of the output to be fed into the $content variable instead of echoing directly.
$content = "";
$content .= '<div id="' . str_replace('_', '-', $box_id . 'Content') . '" class="sideBoxContent">' . "\n";
It may also be possible to output the nav code directly before $content is initialized - experiment if you like. I'm not sure that will work.