I hate to give the answer of "look at the datasheet", but it is going to be your best option. All micro-controllers I have used give their estimated current draw running at various frequencies and voltages. Not all of them will give a graph or equation, but instead will give you a few points in a table. You will just have to interpolate to get what you need.

There is not a single equation that you can use to do this mapping because every device is going to have its own power consumption profile. In fact many embedded devices use their power vs frequency profile as a selling point.

You haven't stated in your question at all, but don't forget about things like LEDs and other external devices connected to your device. These will all effect the power.

After you get a frequency and voltage to run at, you can also use the datasheet to find out how many instructions you can have per second.

You are correct. From Wikipedia:

Examples

A heater rated at 1000 watts (1 kilowatt), operating for one hour uses one kilowatt hour (equivalent to 3.6 megajoules) of energy.

Using a 60 watt light bulb for one hour consumes 0.06 kilowatt hours of electricity. Using a 60 watt light bulb for one thousand hours consumes 60 kilowatt hours of electricity.