What to Target First
I removed some of the sorts which Plan Explorer was originally flagging as the cause. This stored proc is running in about 16 seconds, but needs to be around 2 seconds or less.
At first glance, you have some Key Lookups you should be able to get rid of (included columns on existing indexes). I would start there – often times that can drastically improve performance.
I would look to eliminate the Eager Index Spools. Check the seek predicates and provide permanent indexes where possible.