You don't have to pass anything to paypal and have it passed back. You can just store whatever value you want into the session and it will be available to insert into the database later. We have a random string generator that comes with Data Bridge, but you could easily find a php random string generation function on the web to use as well.
You could save the random string wherever you want. If it is saved per item purchased it might make sense to add a column to the shopping cart and save it when they add to cart. Really where you save it is up to you to support the user experience and end result you are going for... anything is possible.