So if you assume the existence of a ZK proof of knowledge of x (with syntax x_i is the i'th bit of x starting from 0 for the LSB) then ZKPoK{(x):x_i=0} then we can check two most significant bits are 0 with ZKPoK{(x):x_255=0 and x_254=0} by using it twice.

This proof will work on values in some group, we use EC instance of schnorr group (like DSA, same keys, parameters, but simpler signature; DSA is a Schnorr signature variant that offers no advantages over the original AFAIK and many disadvantages that I mentioned in OP).  So we will call the value x where the top two bits must be 0 x_255 = x_254 = 0, and x_{253...x202} are the value in satoshis (same as existing precision) and the remaining values of x_{201..x0} are the private key.

xG will be public and is also the coin public key (slightly different from an existing bitcoin address public key).  Now people can verify that encrypted input values (A,B) add up to encrypted output values (X,C) and fee f, where X is encrypted spend, C is encrypted change and f is fee because A=aG, and A+B=X+C+fG because aG+bG=xG+cG+fG.  This enforces that a+b mod n = x+c+f mod n.  The sender must include ZKPoK{(a,b):a_255 = a_254 = 0}.  The sender must also encrypt x and send it to the recipient so that he can prove information about it when he in turn spends it.  f is public because anyone must be able to collect it and attach it to their address via a mining event.

When the recipient spends xG he will have to similarly prove that x_255 = x_254 = 0.

The reason we need two bits is because n is not a power of two.  Say for simplicity we say n = 250.  Now imagine a=3, b=1, but we have to watch out for fraud by adding n because a+b+n = 254, a+b+n mod n = 4, and x=127,c=126,f=1 so checking only the top bit one could forge value by n as a+b+n = x+c+f mod n   3+1 = 127+126+1 mod 250.  The attacker has increased his value by 250 (minus 1 fee) without using any values with msb != 0.  If we prove top two bits are 0 then we can prevent this attack for up to 3 inputs.  (Because 3*64<250; but not 4 input because 4*64>250).  So for greater than 3 inputs we also prove each intermediate calculation in a 3-ary expression tree also has two msbits=0.  eg where Z(x) is short hand for ZKPoK{(x):x_255=0 and x_254=0}, Z(a),Z(b),Z(c),Z(a+b+c),Z(d),Z(e),Z(f),Z(d+e+f),Z(g),Z(h),Z(i),Z(g+h+i),Z((a+b+c)+(d+e+f)+(g+h+i)) so as mentioned i OP there must be k+log3(k) pair of proofs for k inputs (pair because there is one for x_255=0 and one for x_254).

Finally notice that proving knowledge is a kind of signature so in principle you could pay to another persons existing balance, with their approval, rather than transfer control of a value to a new address.  ie say that your recipient already has a balance y and you want to add x to it for them, you disclose x to them (by encrypting it for their public key say) and then they can add it and therefore you can replace coin addresses by existing balances to save on signatures and keys.

eg ZKPoK[Y]{(a,b,x,y,c),f:a+b=x+c+f and Z(a) and Z(b) and Z(y)}, E(x)

where [Y] indicates an auxiliary signature of some information combined with the PoK.  So the sender is binding his spend of X to say it can be added to existing balance Y (where the sender does not know y). 

Now the block validation will allow the recipient to replace his balance with Y'=Y+X=(x+y)G.  As the sender encrypts the value x for the recipient he can now make onwards transfers.

Taint mixing is also possible (though not that cheaply at scale) by spending dust to some number of other users as a kind of ring-transfer.  (A ring-signature is a scheme where you can implicate without their permission other signers as possible originators of a signature where the originator wants to hide their identity among possible authors).  So thats a bit like coinjoin but you dont need the active collaboration of the other users.  If the E(values) are offchain (eg direct to the recipient) the recipient may or may not even be able to use the extra value, if he doesnt know the dust value (he can reject it by referring only to his previous balance, but that does not disprove that he could still have it in reserve - its hard to prove a negative.)  We could alternatively attach it to the chain (at some size cost) maybe even encrypted with proof that the recipient could decrypt it.  (It is easy to prove xG=xH where H=yG, y unknown to the prover, so EC Egamal could do a provably decryptable value, in which case the software can incorporate the coin and block the owner from using earlier versions).

(dust is a value as now that is considered small, but because x_{202..0} is random by the sender and not computable without DL ability it has to be communicated to the recipient in order to be of value to them).

With mining the original coin is of known value 25 bitcoins (and no dust), however the recipient can still spend it securely without people working out his current balance by elimination by keeping dust as change (which he may never spend as it is has truly negligible fractional nano satoshi values.)

Adam