Odin and Behemoth seem to spawn 36-72 hours after they last appeared. Behemoth will always be level 50 and he is a multi-part FATE that begins south of Behemoth's Domain in Coerthas Central Highlands. You can only get horns from the second part.

Odin's level will vary; each time he is killed he will gain a level. Conversely, each time the FATE is failed he will decrease a level. His FATE has only one part to it and can spawn in any part of The Black Shroud, although there are set spawn locations. Luckily there is a weather effect called 'hopelessness' that accompanies him when he spawns. This effect can be seen in any part of the Shroud, regardless of where he spawns. It cannot be seen from Gridania, however. All possible spawn locations can be seen here (http://imgur.com/a/y26hX). Please note that these images were made using information and images XIVDB (https://xivdb.com/?search/steel-reign) and I do not claim credit for their work!