Hmmm, that's a bit more complicated. I'm sure there's a Macro out there that can do it, but I don't know one off the top of my head.
I think this can be done without a Macro but it will take a little bit of manual work. Here's what I would do:
Place your two sets of keywords in Columns A and B. Select all of Column B and cut (ctrl+x) it. Then in Cell B1, right click, select Paste Special > Transpose. Then, move Column A down one so the list starts in Cell A2.
This will create a matrix with one set of keywords in Column A and the modifiers in Row 1.
Next, in Cell B2, enter this formula:
=$A2&" "&B$1
Copy this across all cells in the matrix and you'll have 10,000 unique keywords. You will then have to remove the formulas by copying the entire sheet, right clicking in Cell A1 and selecting Past Special > Values.
Finally, you'll have to do some manual work of cutting and pasting all the separate columns into one long column of 10k keywords.
I know this isn't exactly what you're looking for, but it's the best I can think of for know. I've updated that spreadsheet example to give you a better idea of what I mean - https://docs.google.com/spreadsheet/ccc?key=0AsNfzI57aVSXdGFKME1pamRnZkJNandZWVpoVkFXZkE
Or, if you want to send your initial set of keywords to me, I wouldn't mind giving it a shot myself. Feel free to send it to tim@prontomarketing.com.
Best,
Tim