I'm not entirely sure if this would work (or work efficiently), but you could use dds.GetDC() to get a DC for your surface, and then use the API call GetNearestColor (see here for details) to find out which palette entry is closest... as I said I'm not convinced it will work but you could investigate it.

Otherwise, you could find your own colour-matching algorithm to find the palette entry in your palette with the nearest colour to one you want. The only way to do that that springs to mind would be a least-square method, or actually you probably wouldn't need to square it... I'll try to explain:

For each colour in the palette, you split it up into red, green and blue components (I'm assuming you're not using alpha), and subtract them from their corresponding red, greed and blue value in your desired colour. Take the absolute value (ie. make negative values positive) of the resulting three numbers and add them together. That sum is a measure of how far away the colour is from your desired colour. You do that for each colour in your palette, and pick out the one that's the closest match.

That's quite possibly a very bad way of finding the nearest colour, I expect there are better ways, but I don't know any.