Troubleshooting a slow performing encrypted stored procedure
Notwithstanding that your question is about how to troubleshoot without decrypting the stored procedure, I would suggest that you do decyrpt the stored procedure so you can do troubleshooting as required, without guessing what's going on.

"Encrypted" stored procedures in SQL Server are actually not encrypted AT ALL.  They are simply obfuscated using a pretty simple method.  This means you can very easily de-obfuscate them and see the source code.  Having said that you might violate the terms of the End-User-License-Agreement included with the vendor's software.  

Use the details found in this question about how to de-obfuscate the "encrypted" stored procedure.

If the EULA forbids decrypting the stored proc, the best course of action would be to contact the vendor to have them do the performance troubleshooting.   You do have a maintenance contract, right?