What is the relationship between power and fuel efficiency?
Unfortunately, the cause and effect in this question is really muddled up. Peter Kampf's excellent answer should explain most of what you need, but it might be that you find his answer difficult to understand because you're still operating under the idea that the stick only manages speed and the throttle only manages altitude. 

If this is the case, please consider this analogy: imagine that there are three buckets of energy available to any aircraft: chemical, potential, and kinetic.  (note for the pedantic: yes, chemical energy is potential energy.  Go away.)


Chemical energy is stored as fuel (dead dinosaurs).  It is released by the engine and can be converted into either altitude or airspeed or both.
Potential energy is altitude below you - the energy which is stored in the aircraft as altitude.  It can be converted into airspeed, but not back into dead dinosaurs.
Kinetic energy is airspeed - the momentum of the aircraft.  It can be converted into altitude, but not back into dead dinosaurs.


As long as the engines are operating, the chemical energy "bucket" is always pouring energy into the other two buckets.  The throttle determines how much energy is poured out per second.  The yoke (stick) determines the distribution of that energy - whether the kinetic bucket is pouring energy into the potential bucket, or vice versa, or neither.

What this means is that if you want to ascend, it's not enough to say that you simply have to pull back on the stick, or that you simply need to increase throttle.  Merely increasing throttle with the nose pointed at the ground does not help you ascend.  Merely pulling back on the stick with the airplane already at the critical angle of attack does not help you ascend.  To ascend, you need to "fill the altitude bucket", which (as Peter says) is always a combination of pitch and power.

As to your actual question regarding fuel efficiency, since it's based on false assumptions I will only say that it depends on the circumstances of the flight, but it is certainly not correct to say that increased fuel consumption is always the result of the greater throttle setting necessary to achieve a higher altitude.