I hope you have posted to the Hungary message board at Ancestry.com. There are a couple of people there who may be able to help you.
The place to begin, as always, is with the most recent info and work back. Ask someone to translate the documents you have you have probably puzzled over them long enough! They may hold clues. Once that is done then you can continue in Hungary. The place you mentioned Debrecen is located 118 miles east of Budapest near what is now the Romanian border.http://www.mapquest.com/maps/map.adp?latlongtype=decimal&...
Also here is a link to WW I Austro-Hungarian land forces which have pictures of uniforms, which may help you.http://www.austro-hungarian-army.co.uk/
And lastly learn a bit about the history of that part of Europe! I can tell you that it will help you in your search.