Change Data Capture and the __$update_mask binary
And the moral of the story is... test, try other things, think big, then small, always assume there is a better way.

As scientifically interesting as my last answer was.  I decided to try one other approach.  I remembered I could do concat with the XML PATH('') trick.  Since I knew how to get the ordinal of each changed column from the captured_column list from the previous answer I thought it would be worth testing if the MS bit function would work better that way for what we needed.

SELECT __$update_mask ,
        ( SELECT    CC.column_name + ','
          FROM      cdc.captured_columns CC
                    INNER JOIN cdc.change_tables CT ON CC.[object_id] = CT.[object_id]
          WHERE     capture_instance = 'dbo_OurTableName'
                    AND sys.fn_cdc_is_bit_set(CC.column_ordinal,
                                              PD.__$update_mask) = 1
        FOR
          XML PATH('')
        ) AS changedcolumns
FROM    cdc.dbo_MyTableName PD


It's way cleaner than (though not as fun as) all that CLR, returns the approach back to native SQL code only.  And, drum roll.... returns the same results in less than a second.  Since the production data is 100 times bigger every second counts.

I'm leaving the other answer up for scientific purposes - but for now, this is our correct answer.