'Search Form' block I would like to add a link called "Advanced Search" below the existing Search box
You could either use the hook_block_view_alter to add the link, just like you say. Or you can implement the search-block-form.tpl.php in your theme and add the link in the template file.