One possible way to reduce the appearance of ears is to extend the thick decorative border out around the edges of the map legend and put a thinner line between the legend and the map (more or less the same as the line that's around the outside of the legend). That treatment would pull the edges into a solid frame while still allowing the legend to be different from both the background and main illustration. The badges that break out at the corners could be pulled in flush with the corners or kept as-is to prevent those outer edges from going completely rectangular.