If your great-grandfather departed Germany from Hamburg, you might be able to find an outbound passenger list from that port. Unfortunately many of the lists for Bremen were destroyed -- it takes space to store records, so they only kept lists for a few years before getting rid of them, and we only have a few groups of records that happened to get saved.
The FamilySearch catalog entry for the collection Germany, Bremen Passenger Departure Lists, 1904-1914 says:
The information contained in this index is for the years 1907-1908 and 1913-1914 only.
The FamilySearch research wiki article Germany Emigration and Immigration gives an overview of the process of emigration from Germany and discusses what kinds of records you might be able to find. It includes information on what emigration records exist for Hamburg and Bremen.
The article is written for people looking for their ancestors who emigrated to the United States, but all the information in the article about German records will be useful to you. When the article gives advice to look in the United States, like this, substitute "in his new country" and look for what you can find in Bolivia.
In order to research your ancestor in German records, you need to know the exact town of origin. Most of the time this information is found in U.S. sources. Thus it is very important to search all available records in the United States first.
Start with the resources in Bolivia first and gather all the information you can -- this will make it easier to identify your great-grandfather in the German records. Look for information in your own family first ("home sources". After that, the FamilySearch Wiki article on Bolivia is a good place to start. Click on the blue button on the main page to see a table of online records.
You have already given us a good deal of information in your question, so you've made a good start. Make a timeline of events for your great-grandfather so you'll have something that is easy to refer to, and make note about where you got the information for each event. Knowing how we got the information is also an important part of the process.
If you need help with German jurisdictions and place-names while searching for records in Germany, the online Meyers Gazetteer is a superb resource.