Is there any way to add a witness without restarting the witness afterwards?
Here's a way to avoid restarting SQL server. It restarts the mirroring endpoint.

Run on the witness server:

--Run the following on a witness server after configuring a witness
USE [master];
DECLARE @Endpoint NVARCHAR(128);
DECLARE @Cmd NVARCHAR(MAX);
SELECT @Endpoint = (SELECT name
                    FROM sys.endpoints
                    WHERE type = 4);
SELECT @Cmd = 'ALTER ENDPOINT [' + @Endpoint + '] STATE = STOPPED;';
EXEC (@Cmd);
SELECT @Cmd = 'ALTER ENDPOINT [' + @Endpoint + '] STATE = STARTED;';
EXEC (@Cmd);


My servers are already in mirroring pairs with endpoints configured only for PARTNER roles.
My witness deployment procedure is as follows:


Add the witness role to each server's endpoint. Each server only supports one endpoint of type four.  

--Run the following on a each witness server before configuring it as a witness to enable WITNESS and PARTNER roles
USE [master];
DECLARE @Endpoint NVARCHAR(128);
DECLARE @Cmd NVARCHAR(MAX);
SELECT @Endpoint = (SELECT name
                    FROM sys.endpoints
                    WHERE type = 4);
SELECT @Cmd = 'ALTER ENDPOINT [' + @Endpoint + '] FOR DATABASE_MIRRORING (ROLE = ALL);';
EXEC (@Cmd);

For Each Server:


Set the witness for each principal database:  

USE [master]
ALTER DATABASE [TODO] SET WITNESS = N'TCP://WITNESS_FQDN:ENDPOINT_PORT';


For Each server configured to be a witness:


Manually fail-over all principal databases so that the server only contains mirrors
Restart the mirroring endpoint on the server to fix connection issues (refer to the script at the beginning of this answer)

After the mirrors have finished any log synchronization backlog, manually fail-over databases as needed so that the primary server is as it was initially.