Assuming your input is everything after ?q=
s/(^\++|\++$|\+\++|[\(\)]+)//g
In those last pair of brackets, you put any other characters you want stripped.
This matches one or more opening +'s, one or more closing +'s, two or more +'s anywhere, or one or more the special characters inside the brackets (so far, just parentheses) and replaces it with nothing – an empty string – zilch – nada.
I don't know jack about Smarty, but I think you should try something like
{$config.siteurl}search.html?q={$tags[row].tag|regex_replace:"/(^\++|\++$|\+\++|[\(\)]+)/":""|stripslashes}
I'm not quite sure if you need to escape the parentheses here, so if it doesn't work, lose some backslashes.