Since it is a more pictorial map, what about a more illustrative border in the same style? Something like looking out an arched stone-block window, or flanking suits of armor on the left and right? I think the borders/legends need to hold their own against the map in the center, and it all has to have some common style. The squared-off borders are too abrupt, and the spears were a good idea but I don't think they're heavy enough.