How do I approach removing menu items on the fly based on settings in my plugin?

Well an easy solution is CSS

<!--    HIDES MENU ITEM IF THE USER IS NOT LOGGED IN   -->
<?php if (is_user_logged_in()){
echo "";}
else {
echo "<style type="text/css">
.menu-item-58 {display:none;}
</style>";
};
?>

But if you are trying to code it down see the source of this plugin http://wordpress.org/extend/plugins/if-menu/ — it will help you alot.

While if you just want a coding answer – a simple one – replace the header

<ul>
  <?php wp_list_pages(); ?>
</ul>

With the conditional statement

if user not logged in
show
<ul>
  <?php wp_list_pages('exclude=17,38' ); ?>
</ul>

where exlude are the pages id you don’t want a not logged in user to see.

while using else commend to show all menu to logged in user

else 
<ul>
  <?php wp_list_pages(); ?>
</ul>

Hope this helps you. keep us up to date.