If you actually have the materials there you can scratch one with the other and see which one is harder.
That is really the correct method. Hardness is also very dependent on impurities as well, e.g. pure Fe and Al
are soft but both have 98% pure commercial alloys that are much harder. It's not as much of a 'pure' property of the elements as other things.
I don't think I buy the denser-is-harder argument. I'm sure it works in some cases, but there are too many exceptions. E.g....
Lithium is harder than cesium. (The metals get softer going down the alkali column.) Gold, mercury and lead are dense but all are soft. Iridium, however, is denser than all them and it is in fact very hard. Copper is harder than silver and gold.
I'd actually guess that Ca is softer than Mg, but my nice Ca sample is sealed in an ampule and I'm not willing to break it out for the correct test.