I can't think of anything that would be helpful in your case (other than trying to ask the newspaper to remove it from their website), but for others in the future here's some tips:
If you have a choice of newspapers, before deciding which one to run your notice in, search the paper's site using terms like "name change" and "change of name" to see if they publish such notices online. This doesn't guarantee that they won't publish old notices in the future (which has happened in a few cases), but at least for now if you choose a paper that doesn't that will help.
Beware of choosing a really unusual name (especially if both the first and last names are). If your name combo is at least moderately common among the general population, it will most likely stay off of page 1 of results (probably behind thousands of others).