story = 'A long foo ago, in a foo bar baz, baz away...foobar'
string_matches = ['foo', 'foo', 'bar', 'baz', 'baz', 'foobar'] # words can be repeated
# story = 'A long **foo** ago, in a **foo** **bar** **baz**, **baz** away...**foobar**'
p story.gsub(/\b(?:#{Regexp.union(string_matches.uniq.sort { |a,b| b.length <=> a.length }).source})\b/, '**\0**')
# If the whole word check is not necessary
p story.gsub(Regexp.union(string_matches.uniq.sort { |a,b| b.length <=> a.length }), '**\0**')
 

c3RvcnkgPSAnQSBsb25nIGZvbyBhZ28sIGluIGEgZm9vIGJhciBiYXosIGJheiBhd2F5Li4uZm9vYmFyJwpzdHJpbmdfbWF0Y2hlcyA9IFsnZm9vJywgJ2ZvbycsICdiYXInLCAnYmF6JywgJ2JheicsICdmb29iYXInXSAjIHdvcmRzIGNhbiBiZSByZXBlYXRlZAojIHN0b3J5ID0gJ0EgbG9uZyAqKmZvbyoqIGFnbywgaW4gYSAqKmZvbyoqICoqYmFyKiogKipiYXoqKiwgKipiYXoqKiBhd2F5Li4uKipmb29iYXIqKicKcCBzdG9yeS5nc3ViKC9cYig/OiN7UmVnZXhwLnVuaW9uKHN0cmluZ19tYXRjaGVzLnVuaXEuc29ydCB7IHxhLGJ8IGIubGVuZ3RoIDw9PiBhLmxlbmd0aCB9KS5zb3VyY2V9KVxiLywgJyoqXDAqKicpCiMgSWYgdGhlIHdob2xlIHdvcmQgY2hlY2sgaXMgbm90IG5lY2Vzc2FyeQpwIHN0b3J5LmdzdWIoUmVnZXhwLnVuaW9uKHN0cmluZ19tYXRjaGVzLnVuaXEuc29ydCB7IHxhLGJ8IGIubGVuZ3RoIDw9PiBhLmxlbmd0aCB9KSwgJyoqXDAqKicpCg==