Son Frederick was born when Nicholas was 13?! Are you certain?
The Winona Newspaper Project will probably be of help to you, although perhaps not for determining Katherina's maiden name. A quick search brought up the obituary for Nicholas in 1880.http://digital.olivesoftware.com/Default/Skins/WinonaA/Clien...
It works best to do an advanced search: put in Krieg, "All Clippings", "Search in all Publications", and sort by date ascending.
The website usually loads very slowly, so be patient.