Are results that are derived simply by using more computational power publishable?

(I switched the order of a couple of your questions to give the answer a more logical flow.)

On the other hand, the results are definitely new, and interesting (for whatever reason N = 20 is the point where interesting effects are predicted).

If the results are new, and interesting, then they are by definition publishable. The key point is they add something meaningful to the sum total of human knowledge. That’s certainly a sufficient criterion for publishability (in an idealized sense it should be necessary as well, but I fear it isn’t - plenty of things get published that don’t really meet this condition).

Are Bob's results publishable? He didn't actually do anything special, he just had more computational power.

The concept of “doing something special” is both mostly meaningless and (to the small extent that it has any meaning) completely irrelevant to the question of publishability. Plenty of authors of excellent papers “didn’t do anything special” - they just had more patience and were willing to work a bit harder, or in many cases just got a little bit luckier, than their peers, and ended up discovering something significant. Publication is not a prize that’s given for “doing something special”, it’s simply the scientific community putting a stamp of approval on a discovery that it is correct, new, and worth paying attention to.

By the way, one can even say that a researcher Bob who works harder than his peer Alice is pretty much the exact scenario you are describing of someone “having more computational power”. In this case the computational power is of the human sort, but I don’t see why that should change the calculation.

Edit: another thought is that Bob actually did “do something special”. It’s not just that he had more computational power, but he had the foresight and intuition to realize that it would be worthwhile to apply that computational power to Alice’s particular problem rather than spend his time and resources doing any number of other things. So although it’s not really that important as I said above, even by your own criterion I think there is more merit to the achievement than your description makes it sound.

If they are publishable, what would Bob actually write in such a paper? Everything sans the result could effectively be communicated in one sentence ("Read Alice's paper").

Bob would simply write what he did and what the results were, and what makes them interesting. If it can really be described in one sentence I’d argue that it likely wasn’t such an interesting result after all. But on the off-chance that it was indeed interesting, then it would make for a great one-sentence paper. There isn’t any rule that papers have to be longer than one sentence.

Papers like this can be published, and can be extremely important

There is no inherent reason why a paper of this nature would not be publishable, and indeed, there are some examples where papers of this nature have been published in high-ranking journals and have been extremely important papers. Whether a paper of this nature is publishable largely depends on the importance of being able to compute outcomes of the problem to a higher level. In some cases this will be unimportant, and the paper would be rejected; in other cases it would be extremely important, and the paper could become an important work in the field. Note also that the mere fact that the additional computation does not involve "anything special" from a theoretical standpoint, is often quite irrelevant to the importance of the result.

The most obvious example I can think of here is Shaeffer et al (2007) Checkers is solved. This paper was published in the prestigious Science journal. It extended earlier works computing the game-theoretic solution to the game of checkers. In this paper the authors had managed to obtain sufficient computing power to (weakly) solve the game, and this was a major innovation in the game-theoretic analysis of checkers. According to the authors:

The effort to solve checkers began in 1989, and the computations needed to achieve that result have been running almost continuously since then. At the peak in 1992, more than 200 processors were devoted to the problem simultaneously. The end result is one of the longest running computations completed to date.

In this particular case, the additional computing power accruing over time made the difference between early calculations that could not solve the problem, and later calculations that constituted a solution. This particular paper only weakly solves checkers (meaning that it gives perfect play from the starting point of the game, but it does not give perfect play from every possible board state). The next expected innovation would be to strongly solve checkers (i.e., find perfect play from every possible board state), and I imagine that the team that does this will also get an excellent publication in a high-ranking journal.

In addition to the excellent answers that have already been given, the question indicates to me a common misunderstanding what papers actually are. They are, or at least should be, the communication of ideas, results, or some other type of knowledge that may be of interest to others. They are not badges of honour or grades or brownie points for doing X atomic units of research. In that sense, "how much work was it?", "how difficult was it?", or even "how large is the delta to existing work?" are fundamentally not the right questions to ask when evaluating whether something is publishable. If you have a stroke of genius and write down a cool idea very quickly, it's value to society is in no way diminished. Conversely, spending a lot of time on a bad idea does not make it more valuable to society.

However, as I wrote initially, it's an easy mistake to make because there is, of course, a correlation between effort/complexity and value/interestingness. Simple ideas are not often extremely valuable, because the chance that somebody else had the same idea before is high.

Apply this thinking to your question:

Are Bob's results publishable? He didn't actually do anything special, he just had more computational power. On the other hand, the results are definitely new, and interesting (for whatever reason N = 20 is the point where interesting effects are predicted).

Doing "anything special" isn't in truth what makes papers accepted. If there are interesting effects to be observed for N=20, then go for it. That said, to my ears it does sound a bit suspicious that all that was needed to resolve an open question that people actively find interesting is to throw a little more hardware at it. I would make quite sure that indeed nobody has done it and that there are indeed interesting effects to be observed (and then I would still wonder a little why nobody has done it yet, unless the paper you build upon has appeared like a week ago).

If they are publishable, what would Bob actually write in such a paper?

Summarize the original work to the extent that is needed to actually follow your paper (given the setup this may be quite a lot more detail than what you would typically dedicate to previous work - that's ok, as long as you make it clear that these are not your new results). Describe your setup and experiment. Then, if the interesting results for N=20 are what should carry this publication, describe these results and in which ways they are interesting in a lot of detail. Connect them to previous results for smaller Ns, and, if possible, go to the bottom of why the results start becoming more interesting for higher Ns.

If that does not give you enough "meat" for a normal conference or journal article, there are alternative publication venues dedicated to shorter articles, such as journal notes.