I didn't use a guide of any kind in my first play through, so I would search for these marks using only the information given in the game. King Behemoth took me a few hours to find, and when it's hulking outline appeared through the mist and snow I jumped out of my skin. I was quite low level when I tackled him, it was a long tricky battle but much enjoyment was had. I remember positioning my characters so that only the tank gets hit with it's area of effect magic, and every time it readied it I would open the menu and temporarily equip an Aegis shield.