There is no easy way to find all of your status updates with a location. Facebook's graph search currently does not support searching through your posts/status updates. If you try typing in either "my posts at" or "my status updates at" in the top search box, Facebook will say "This search isn't available yet." (The graph search does support location searches for other things such as photos - if you type in "my photos at" then it will suggest searches for your photos taken at various locations.)
Right now I think the only way for you to find all of your status updates with a location is to go to your Timeline, load all of your status updates, and then use the browser's Find function.
So first, go to your Facebook profile, and it will load the Timeline portion of your profile by default. Then keep scrolling down until you get to the very bottom, which will be your earliest status update. This may take a while if you have a lot of status updates. When you finally get to the bottom, Facebook will have loaded a lot of your status updates, but not necessarily all of them. Sometimes it only loads your "highlights" for certain months or years. So use your browser's Find function (should be CTRL-F in Windows or Command-F on a Mac) and search for "HIGHLIGHTS". Every time you find "HIGHLIGHTS" on the page, click the little down arrow next to it and "All Stories" will appear. Click on "All Stories" to force Facebook to load all of your status updates for that period:

After you have clicked on "All Stories" for each instance of "HIGHLIGHTS" that appeared on the page, you will have loaded all of your status updates. Then the matter becomes finding the status updates with a location. Based on what I've seen, Facebook can use " at " or " in " to indicate the location of a status update. You can see this from the following examples:

So you should use your browser's Find function to search for the strings " at " and " in " (with the spaces around the words) throughout the page to find your status updates with a location. Obviously you'll find every occurrence of " at " and " in ", and some of those might not be status update locations, so you'll just have to skip those. Every time you find a status update with a location you want to remove, click the down arrow on the upper right corner and click on "Change location" and then delete the location:

Unfortunately there is one more way that Facebook can indicate the location in a status update, and that is shown in this example:

As you can see, there's no " at " or " in " or any other words next to "New York, NY". So the only way to find this type of location in a status update is to search for the name of the location itself, which means you will have to remember all of the locations that were ever saved in your status updates. This will be a pain, but there's no easier way to find these locations.