Protecting your Tweets only protects your Tweets going forward. When you protect your Tweets, all Tweets posted after you save your changes will be protected and not shown in Twitter search or third party applications.
All Tweets posted before protection, will still be shown in Twitter search, search engines, and third-party applications.
To find out how to remove your updates from Google search, check out this article. Twitter does not have the ability to remove content on websites other than Twitter.com.
After you protect your Tweets, only approved followers can read your updates.
What If my Tweets have never been public?
If your Tweets have never been public (in other words, you've always had your Tweets protected in your settings), your updates should never show up in Twitter search or other public search engines.