Even though you are trying to perform an update on the records you can think of your multiupdate page like a results page. So the idea is to get it to limit the records that are shown on this update page to be only the records to update.
On the page with the checkboxes you need to add in the brackets after the name like this:
<input name="product_id[]" type="checkbox" id="product_id" value="<?php echo $row_WADAwProd_Bread['product_id']; ?>" />
Now on the page that you have added the DataAssist Search server behavior to you will need to update it to work with this form element and specify the type of search as a list type. When the form is submitted to this page it should only contain records for the items that you selected.