Ok, revised spec:
SPEC:
message PaymentDeatils {
...
optional uint64 minfee tag number=8
Pay at least minfee satoshis in transaction fees. Wallet software should add minfee to the amount the user authorizes and pays, and include at least minfee in the transaction created to pay miner's transaction fees. Wallet software may request that the user pays more, if it must create a complex transaction or judges that minfee is not sufficient for the transaction to be accepted by the network..
:ENDSPEC
Making it fee-per-kilobyte is a bad idea, in my opinion; users don't care how many kilobytes their transactions are, and they will just be confused if they're paying for a 10mBTC burger and are asked to pay 10.00011 or 9.9994 because the merchant has no idea how many kilobytes the paying transaction will be.