When did Germans start write nouns with a capital letter?
Not only Germans does it, but everybody who writes in German language. (German is official language of Austria, parts of Switzerland, Liechtenstein, parts of Italy and many other regions too, where mainly people live who are not Germans, and they all write nouns with uppercase first letter when they write texts in their native language.)
2000 years old tablets from the Roman Empire bearing inscriptions in Latin language are relatively easy to read for us because we know all the letters that were in use in those ancient times. We use them as uppercase letters today.
But also our lowercase characters have their origin in the old latin alphabet. The development of these letters as a distinct alphabeth begun in 4th century.
Carolingian minuscule is an alphabet from 8th century that only consists of lowercase letters and in the next centuries it became the dominant alphabet in Europe.
But writing was a skill only known to privileged people. And one of the most important things to write were copies from the holy bible. But when monks wrote copies of the bible, they wanted to make it as beautiful as possible, and so they begun to write the first letters of each chapter (the so called initials) in a different alphabet. They used letters from the old roman alphabet, because their origin is the many centuries old Latin language, which is also the language of the bible (at least of the New Testament).
And so it happened, that two different alphabets merged into a new alphabet where every letter existed in two versions, which was a completely new invention. There was one version used for initials, and the other for "normal" letters.
The practice of writing the first letter in the old roman alphabet (which was also called "majuscle alphabet") while the rest was written in the relatively younger minuscule alphabet got used for texts written in German language too. And soon some writers wrote the first letter of every word in majuscle letters, similar to modern English title case.
But most authors only wrote "important" words with an uppercase initial while less important words were written in all lowercase letters. (Also here you will notice similarities to English title case.) But the "important" words are most likely words that appear as the core of subjects and objects, and these words are nouns. And this is why in the 17th century it became a rule of thumb to write nouns and the first word of each sentence with an uppercase first letter and the rest in lowercase letters. (There were no "official" orthographic rules for writing German texts before 1876.)
This rule in first place was a part of the baroque ideal to decorate anything and everything. It was more a kind of rule of decoration (as it also was before) than an orthographic rule. But in the baroque epoch it turned into an orthographic rule too.
The rule to write the first letter of every sentence in uppercase letters became part of orthographic rules in all languages written in this mixture of two alphabets (the old roman majuscle alphabet and a newer set of letters derived from the Carolingian minuscule alphabet). But the writing of nouns this way was only used in Danish and German language. But Denmark decided in the Danish orthography reform of 1948 to suspend this rule for nouns, and so only German language is still using this rule.