The Germans established successful overseas colonies in the Eastern Baltic during the High Middle Ages. Of course they weren't controlled by the home country in quite the way modern colonies were. (And they could have gotten there by land in theory, but in practice they got there by sea voyage.) See the Wikipedia articles on Baltic Germans and on the Northern Crusades.

Or, if Scandinavians count as Germans, the colonization of Iceland would be an even earlier example.

Germany was busy influencing Eastern Europe all the time from year 1000 and onward. You had german influence far and wide. Prussia reached almost all the way to Russia. Bavaria had serious influence into Böhmen und Mähren. Austria focused a bit more southward Hungary and southeast into Balkans. People high up spoke German in lots of now slavic cities, Prag(Praha), Laibach(Ljubljana), Königsberg (Kaliningrad), Danzig (Gdánsk), Breslau (Wroclaw).

So much busy doing this it did not even unite until 1870 which was very late by the colonization power's standards.

Almost all of Central- and Eastern Europe was in practice German around 1900 and it required basically two huge world wars for the colonial powers to remove this German influence and try to hush-hush this fact and swipe it under the rug.

As others have stated, Germany wasn't unified until after all the good bits were taken.

There's also the fact that Germany has easy land borders[1] with relatively powerful[2] countries on three sides who were usually rivals if not outright enemies. It's harder to go conquering far-off places when you need to keep lots of troops for home defence. Of course it's also easier to invade those countries too, as has been demonstrated several times. Why invade India when you can pinch a bit of France or Poland which are right next door?

[1] Whereas Britain is an island, Spain is nearly one (and has mountains along the "neck"), France has sea along the side facing Britain.
[2] Individually enough to be a nuisance, and dangerous if they band together.

You need a navy to project force overseas. Historically, the region which later became Germany didn't have that navy for several centuries, and I think this isn't just accidental but also has good reasons.

• Germany doesn't have that much shoreline to begin with. Half that shoreline is on the Baltic sea which is locked up behind the Danish Straits. The other half still must get through English/French waters in the Channel, or English/Scandinavian through the GIUK gap. Of the 5 examples you gave, 4 have established ports directly to the Atlantic. Netherlands is the exception, but for a long time it had an advantageous standing as a trade empire and enjoyed decent relations with one of the other great powers, such as England. In the 1700s, the English tolerated Dutch movement through their chokepoints, but not German, due to geopolitical concerns.
• For the other colonizers, naval activity was always key to survival. England was obviously reliant on ships being an island. France and Spain had ports in the Mediterranean. Portugal and Netherlands relied on maritime trade. German naval tradition was actually also pretty strong in Medieval times. The Hanseatic League for example was doing quite well, and would have probably built a strong German trade presence overseas, but unfortunately it went into decline just as the New World was being discovered. With how much land Germany had, and no Mediterranean ports, land trade was always an attractive alternative as well.
• Without a powerful state navy (whether your own government's or an ally's) it is hard to do global commerce as piracy, privateering and tariffs destroy your profits. In the age of sail, there wasn't really a Germany to provide this navy. HRE was too much of a mess and distracted by concerns on the continent to develop one. Other powers didn't want to protect it either. The Dutch were part of HRE until the 17th century, but interestingly enough their colonial activity ramped up after they left. In the second colonial period during the Victorian era, Germany was becoming more unified, but whenever they tried to build a navy the English would repeatedly suppress them - understandably, since losing naval dominance to Germans would be death for the English.
• As others pointed out, Germany was a lot less unified politically until very recent times. Even Prussia wasn't that powerful when the race for Americas was starting, by the time it managed to solidify politically, the easy pickings were already taken by stronger empires. Prussia was also kept busy with many big land wars, which were less of an issue for countries like England or Portugal.

So I would say the main reason "Germans" missed the boat (see what I did there?) to the Americas is that the Hanseatic League collapsed just before the race was started. If Columbus was born a hundred or two hundred years ago, things would probably have been much different. Not only were German naval traders much more active at that time, but rivals like England, Spain and others were much weaker. Funnily enough, individual Germans still immigrated to America in large numbers, and Germany could have possibly pursued a claim on that basis, had a "Germany" had existed at that time and possessed the military to press that claim.

During the race for Africa Germany actually did about as well as you could expect given its limited shoreline, distance, and lack of naval power. Once it unified in late 1800s, it gradually came to control several African states like Namibia. The problem came about with WW1: England and France won, so they got to keep their colonies while Germany's were "liberated" (well, from German rule, at any rate). WW1 also wiped out the German navy and destroyed their economy, preventing any subsequent attempts, and after WW1 colonies began to fall out of fashion anyway. So the big "what if" event here would have been Germany either staying out of WW1 or not losing. For example Belgium held on to Congo - even though Germany invaded them in WW1, at the end of the war the Allies allowed them to keep it, in fact they were given some of Germany's colonies. Something similar happened even in WW2 (incidentally, France was also devastated but held on to Algeria until the 60s). So I would say the main point where Belgium (and France) "succeeded" and Germany failed was being on the losing side of a world war.

While WW2 is not really a colonial period, during this time Germany had ample access to the Mediterranean via France and Italy. At one point it did control a significant part of North Africa. If Germany had not lost WW2, that would have certainly resulted in German control of many North African regions like Algeria, and possibly parts of India coming under German sphere of influence. Granted, it seems even harder to imagine Germany staying out of or winning WW2 compared to WW1, but at the end of the day I would say the main reason Germany couldn't colonize Africa failed was losing wars against countries that could.

According to Wikipedia's List of Largest Empires https://en.wikipedia.org/wiki/List_of_largest_empires1

The German Colonial Empire in 1912 had an area of 3.199 million square kilometers or 1.24 million square miles and covered 2.15 percent of the Earth's land surface.

Among European colonial empires the German Colonial Empire in 1912 was smaller than:

The First French Colonial Empire in 1670 (3.4 & 1.31, 2.28 %).

The Italian Colonial Empire in 1938 or 1941 (3.798-4.25 & 1.47-1.64, 2.55-2.85 %).

The Second Portuguese Colonial Empire in 1820 or 1815 (5.5-10.4 & 2.12-4.02,3.69-6.98 %).

The lands of the Iberian Union in 1640 (7.1 & 2.74, 4.77 %).

The Second French Colonial Empire in 1920 (11.5 & 4.44, 7.72 %).

The Spanish Colonial Empire in 1810 or 1750 (13.7-20.0 & 5.29-7.72, 9.20-13.43 %).

The British Colonial Empire in 1920 (35.5 & 13.71, 23.84 %).

Among European colonial empires the German Colonial Empire in 1912 was larger than:

The Third Portuguese Colonial Empire in 1900 (2.1 & 0.81, 1.41 %).

The First Portuguese Colonial Empire in 1580 (0.80 & 0.31, 0.54 %).

Note that the Belgium Colonial Empire, the Dutch Colonial Empire, the Danish Colonial Empire, and the Swedish Colonial Empire are not listed.

So some persons might believe that the German Reich did rather well in acquiring colonies despite being such a johnny-come-lately in the colonial race.

German Empire

The German Empire arrived too late. It was created in 1871, when much of the world had already been divided. Maybe Germany could have tried to gain a larger share during the Scramble for Africa which started in the 1880s. However, colonial expansion wasn't considered a priority by long-time chancellor Bismarck.

This changed when Bismarck was dismissed in 1890. Kaiser William II. considered colonial expansion an absolute priority. Under his rule Germany acquired several colonies in Africa and a few tiny territories in Asia. In 1919, after World War I, Germany had to cede its colonies to France and Britain. Thus, the history of Germany as a colonial power is rather short, about 30 years, and had less of an influence on German society and culture.

Why didn't Germany play a role in earlier times?

There could have been colonies by other, older German states. There were many - actually, hundreds - of German states and statelets that could have acquired colonies. Most of these states were landlocked, though.

The map below shows the Holy Roman Empire in 1648 - at the end of the Thirty-Years War. Which territories could have tried to become a colonial power?

• The formerly powerful Hanseatic League (Hamburg, Bremen, Lübeck and other towns) had sunken to irrelevance - at least relative to their power in the 15th century when they controlled the maritime trade in Northern Europe.

• The Electorate of Brandenburg, the later Prussia, possessed a larger stretch of land along the Baltic coast. Unfortunately, Sweden still controlled the estuary of the river Oder and thereby the main port for its exports.

• Other principalities were too small and/or governed by monarchs of other countries (Spain, Denmark, Sweden).

Source: ziegelbrenner (@WikimediaCommons) CC BY-SA 3.0

This doesn't mean that Germany didn't play any role:

• Venezuela (or Little Venice) had been a colony of a German family for about twenty years (1528 -1546). The Welser dynasty had received a title over a large piece of land along the coast of South America for helping the Spanish king Charles I to become Charles V of the Holy Roman Empire. However, their (German) conquistadors didn't find any treasures of gold or other source of revenue until they had to surrender their claim.

• There had also been some other ill-fated attempts to found colonies in Africa or America. For example, Brandenburg was temporarily involved in the slave trade.

This question assumes a 1913 viewpoint and relies on nationalist definitions of a state and its 'colonial empire'.

That is a bit problematic.

Take the Dutch Colonial Empire as an example: when that started, with its origins listed as 1543–1652, the Dutch Republic was part of the Holy Roman Empire.

The first German colony was a private enterprise, not unlike Virginia, when the ruler of Spain, the Habsburg Holy Roman Emperor Charles V granted the Welsers in 1528 to establish 'something' in Venezuela. This capitalist endeavour failed mainly due to mismanagement.

The Bavarians wanted to colonise New York when the city that was there was still called Nieuw Amsterdam.

The early Brandenburg-Prussia colonies in Africa were initially 'successful' in enslaving people and partaking in the triangular trade, but the repeated failures of the weak Navy to establish its own turf in the Carribean lead to a recalculation of profitability. This together with Frederick Williams hobby of collecting soldiers on land close to home led to simple abandonment of such projects.

If we abandon the outlook of nationalism and high imperialism, which doesn't project well back to the start of colonisations, then we see the following dates: German King & Holy Roman Emperor Charles V (reigned –1556):

Charles initiated his reign in Castile and Aragon, a union which evolved into Spain, in conjunction with his mother.

What is called

The Spanish conquest of the Aztec Empire, or the Spanish–Mexica War (1519–21), was the conquest of the Aztec Empire by the Spanish Empire within the context of the Spanish colonization of the Americas.

Is really anachronistic as well. As:

Castile became the dominant kingdom in Iberia because of its jurisdiction over the overseas empire in the Americas and the Philippines. The structure of empire was established under the Spanish Hapsburgs (1516–1700) and under the Spanish Bourbon monarchs, the empire was brought under greater crown control and increased its revenues from the Indies. The crown's authority in The Indies was enlarged by the papal grant of powers of patronage, giving it power in the religious sphere.
An important element in the formation of Spain's empire was the dynastic union between Isabella I of Castile and Ferdinand II of Aragon, known as the Catholic Monarchs, which initiated political, religious and social cohesion but not political unification. Iberian kingdoms retained their political identities, with particular administration and juridical configurations.

Then the treaty of Zaragoza 1529, legal Dutch independence from HRR 1648. Result: In 1530 half the world was destined to be colonised by people whose sovereign was a German king and Roman Emperor.

In summary, while there were somehow German colonies, or rather Germanic, as no German nationstate existed, with varying degrees of success, there was no concerted and sustained effort to systematically expand these for the first few hundred years. Until Bismarck was carried to the hunt by nationalist imperialists. As already noted in Steve Bird's answer, the naval support of overseas possessions was also a constant problem. The Bavarian Navy knows what that means.

In order to support a global empire, you need to be capable of supplying and defending your outposts with a strong Navy. The five other European nations that you named all had long naval traditions and the growth and decline of their empires reflect their respective abilities to support and defend their overseas assets.

Failing to recognise the importance of the navy in this respect was one of the reasons that Spain's empire declined as those of Britain and France started to flourish.

Given their position within Europe, the German states didn't have strong naval traditions and, therefore, didn't have the power to project their power and protect overseas colonies (and trade routes). It was only after German unification and the growth of a German Navy that they were able to compete with the other European empires. By which time, of course, most of the claimable lands in the world had already been taken (and, in some cases, already lost) because the other empires had a few hundred years head-start.

Additional Reading:
The Influence of Sea Power Upon History: 1660–1783, A.T.Mahan (1890)
The Influence of Sea Power upon the French Revolution and Empire, 1793–1812, A.T.Mahan (1892)

Which Germany do you mean?

Something that can reasonably called a German nation-state was founded only in 1871, when Prussia first defeated France and then unified most German states under their leadership in the Kaiserreich.

Before there had been a messy rivalry between Prussia and Austria for the leadership in what used to be the Holy Roman Empire -- not very holy, not very roman, and not much of an empire. That was concluded in Austro-Prussian War of 1866, when Prussia kicked Austria out of the slowly forming Germany.

The Kaiserreich was at first heavy influenced by Bismarck, who believed that Germany was better off without colonies. At the time, this probably was a correct estimate. Those colonies that could have been seized were not worth the effort. Bismarck was fired by Wilhelm II, whose expansionist policies contributed to the tensions which led to the First World War.

So Germany missed the early rounds of colonialism because it wasn't there.