Oh yes, I usually call it a compass rose or something. English is my second language after all.
It depend how complex you want it to be. You could use for example, different stars shapes or the same one with different sizes. Make sure they all have the same center and rotate them to have the main direction N,S,E,W WITH THE BIGGEST POINTS. Smaller points indicate other direction like North east. Put the different shape of different colors for some effects. White and red are two colors frequently used.

About the mesure, you can do it in a vector program or even with something else using simple rectangles usually black and white. Dupplicate them to make sure they have the same dimensions. Then add a line around to make them stand out. Just add the numbers and that's it. Of course, to fit the map you could replace the black with brown or beige and maybe some texture like your map border.