Ok, so the solution is
1) Although the opposite is documented for the antecedent step (getting a token ID), for this specific request, FPS cares about the case of the parameters - they should all be camel case.
2) I was missing a default '/' to cover the case of a blank path in my message signing function (the endpoint here has nothing after the host name)
Here's the HTTP GET that worked (obfuscating AWS credentials)
https://fps.sandbox.amazonaws.com/?AWSAccessKeyId=AKIAIEXAMPLE
&Action=Pay
&CallerDescription=MyWebsite
&CallerReference=0.7753969375044107
&SenderTokenId=25R7R3NUFBS6VPRZV5Z53AWP2YLNXAYEPFJ8BCDGMXH4V1FPMZZ95VATZLEFUCPG
&SignatureMethod=HmacSHA256
&SignatureVersion=2
&Timestamp=2013-07-06T14%3A38%3A41-07%3A00
&TransactionAmount.CurrencyCode=USD
&TransactionAmount.Value=3
&Version=2008-09-17
&Signature=Ijf0hqQuSi5zU%2BF1PUK1LBYvsK9AVHacrqK1hJVzffk%3D
And here is the message as it was actually signed with Hmac SHA256 (AWS Secret key as password):
GET
fps.sandbox.amazonaws.com
/
AWSAccessKeyId=AKIAIEXAMPLE&Action=Pay&CallerDescription=MyWebsite&CallerReference=0.7753969375044107&SenderTokenId=25R7R3NUFBS6VPRZV5Z53AWP2YLNXAYEPFJ8BCDGMXH4V1FPMZZ95VATZLEFUCPG&SignatureMethod=HmacSHA256&SignatureVersion=2&Timestamp=2013-07-06T14%3A38%3A41-07%3A00&TransactionAmount.CurrencyCode=USD&TransactionAmount.Value=3&Version=2008-09-17