Here's what I would look at...
Pages Menu
Look in your header.php. Find the lines of code that specify the pages menu in the upper right of your displayed header. They will most likely look like this, and may be at the top of the lines below the <head> section:
<div id="menu">
<ul>
<?php wp_list_pages('title_li='); ?>
</ul>
</div>
Back up the entire contents of header.php so you can go back if things don't work out.
Cut and paste this code to the bottom of the lines below the <head>, above the last </div>.
The <div>, <ul>, and <li> are listed in your stylesheet (most likely style.css) for the appropriate id's or classes, and determine how the menu looks and how it's postioned. It's probably floated to the right with no margin.
If floated to the right, you want to float it to the left. Margins or padding may need to be changed or adjusted to make it look right. This is done with the values in the stylesheet. Again, make a backup so you can go back if things don't work out.
Categories Menu
If everything goes right, you can add the categories to the menu. To do that you add this function, `<?php
wp_list_categories('title_li='); ?>`. The entire menu code would be like below:
<div id="menu">
<ul>
<?php wp_list_pages('title_li='); ?>
<?php wp_list_categories('title_li='); ?>
</ul>
</div>
If everything works to satisfaction, you can then delete or comment-out the menu in the upper right.
Okay, this is just an example, and your code in your header.php and style.css is probably different. It may be confusing. So, you may want to start with the WordPress documentation here, specifically "Design and Layout".
Good luck!
Note: This is the same as above but some typos were corrected...