By "in principle" I am excluding any consideration of running time, or computing resources. For example, if k = 10, perhaps you would need a computer with 10^10000 bytes of RAM working for an equal number of years. It's a finite computation. ;)

"may not even halt" corresponds to my "it looks like". Such algorithms not working would be equivalent to me and the parent commenter being wrong -- which is not out of the question. Probabilistically, such an algorithm should work (I think -- have not checked the details), so it ought to work unless there is some unforeseen reason why it wouldn't. A "conspiracy" against this happening, if you will.

As far as the difficulty in counting twin primes -- well, to give an easier example, look at Cojocaru and Murty's book on sieve methods and read about the sieve of Eratosthenes-Legendre. You know that 1/2 of numbers are even, 2/3 aren't divisible by 3, 4/5 aren't divisible by 5, etc., so the proportion of numbers that are prime is equal to (1/2)(2/3)(4/5)(6/7)..., which you can show with a little bit of effort is equal to 0.

With some work, you can turn this into a proof. In theory, you can estimate the number of primes < X, as a function of X. This estimate would be roughly along the lines of the original post. But as Cojocaru and Murty (among others) point out, the error terms get bad quickly. This type of phenomenon is extremely common in analytic number theory.

In the case of prime counting, you can get better results by other methods, most prominently the Riemann zeta function. But even then you can only get the best results if you prove the Riemann Hypothesis. Million dollar bounty out on that one.