This formula should work.
"+1 " & SUBSTITUTE(SUBSTITUTE(SUBSTITUTE({Phone #}, '(', ''), ')', '')," ","-")
It finds and removes the parentheses with the SUBSTITUTE function, then finds the remaining " " (Space) and replaces it with "-". Then you just use the "&" operator to add "+1 " to the front.
Hope that helps!