Nedávno jsem řešil stejnou situaci. Liší se to úřad od úřadu. Záleží na tom, jak dobře si úřednice pročetla zákon. Já musel mít:
Nákres stavby
Textový popis
Vyjádření od vodovodů, elektriky at. mně stačilo čestné prohlášení, které jsem napsal, že tam žádné sítě nejsou
Zákres stavby v katastrální mapě (stačí rukou, jen jak to je daleko od sousedních pozemků)
Pokud jsou sousedi, tak jejich souhlas. (Ještě je třeba aby stavba byla dále jak 2m od sousedního pozemku, jinak to je zase složitější)
Samotný formulář ohlášení stavby
Vyjádření z krajského úřadu ze životního prostředí

Krajský úřad i Městský úřad na to mají 30 dní. V době dovolených to bohužel opravdu trvá skoro těch 30 dní.

Pokud byla kůlna postavená legálně ta by ještě mělo být povolení k demolici :)

Jediné co mě na všem uklidňovalo, že se za nic neplatily poplatky.