Interesting article in the Asahi Shinbun about a kozuka (sword accessory) decorated with cranes (orizuru):
http://www.asahi.com/ajw/articles/AJ201703140003.html This pushes back the earliest record of an origami crane to around 1600 CE or thereabouts. Origami historian Masao Okamura comments in the article. Robert