Everything was really straight forward right up until that locked fence in westland. Been around the map 3 times looking for a key or a boss to fight for it! Any... Hints or riddles you can give out to help me?

you get it after a hidden boss fight in the starting area!

You don't need that key to finish the game, iirc. It unlocks another boss (who is probably the hardest in the game, but is easy to cheese)