Can faster processors/clocks execute more code?
In general the number of assembly instructions the device can execute per second will depend on the instruction mix and how many cycles each instruction type takes (CPI) to execute. You could in theory cycle count your code by looking at the disassembled asm file and looking the function you are concerned about, counting up all the different types of instructions in it, and looking up the cycle counts from the datasheet for your target processor.

The problem of determining the effective number of instructions per second is exacerbated in more complex processors by the fact that they are pipelined and and have caches and what not. This is not the case for a simple device like an ATMega328 which is a single instruction in flight processor.

As for practical matters, for a simple device like an AVR, my answer would be more or less "yes". Doubling your clock speed should half the execution time of any given function. For an AVR, however, they won't run faster than 20MHz, so you could only "overclock" your Arduino by another 4MHz.

This advice does not generalize to a processor which has more advanced features. Doubling the clock speed on your Intel processor will not in practice double the number of instructions it executes per second (because of branch mis-predictions, cache misses, and so forth).