I quite like the first compass doodle you did in the somewhat sword shape as it mixes the definitive points and curves of a celtic knot to good effect. Out of your new ones, I agree that the third one along is the best. I don't really knows where you can look for designs, but I'm sure you can tweak a few designs together into a completely original one!

On your second point, I definitely see your dilemma and agree a key would be the best solution to it, though there is no space. Are all the buildings of equal value? Perhaps the map could just label the key ones e.g. the smithy, the inn, the chieftain's hut, etc? That way the labels wouldn't dominate the map so much even if it didn't give full understanding of the map. It's up to you if you choose to label them digitally or not (personally I always like doing all the text and what not by hand and then only use digital to tweak and correct bits and pieces, but that's just me ). Digital is always good though if you're not happy and then can change to a key or a couple of labels or whatnot, so it's got a lot of room for flexibility to suit your needs.

I hope this helps in some way or another and I am sure whatever you end up choosing it will look great!