Does Assigning Stored Procedure Input Parameters to Local Variables Help Optimize the Query

Why would replacing a parameter with a local variable speed up a query

It is a "parameter sniffing" workaround. I recommend to read: Slow in the Application, Fast in SSMS?

Parameters and Variables
Consider the Orders table in the Northwind database, and these three procedures:

CREATE PROCEDURE List_orders_1 AS
   SELECT * FROM Orders WHERE OrderDate > '20000101'
go
CREATE PROCEDURE List_orders_2 @fromdate datetime AS
   SELECT * FROM Orders WHERE OrderDate > @fromdate
go
CREATE PROCEDURE List_orders_3 @fromdate datetime AS
   DECLARE @fromdate_copy datetime
   SELECT @fromdate_copy = @fromdate
   SELECT * FROM Orders WHERE OrderDate > @fromdate_copy
go

In the first procedure, the date is a constant, which means that the SQL Server only needs to consider exactly this case. It interrogates the statistics for the Orders table, which indicates that there are no rows with an OrderDate in the third millennium. (All orders in the Northwind database are from 1996 to 1998.) Since statistics are statistics, SQL Server cannot be sure that the query will return no rows at all, why it makes an estimate of one single row.
In the case of List_orders_2, the query is against a variable, or more precisely a parameter. When performing the optimisation, SQL Server knows that the procedure was invoked with the value 2000-01-01. Since it does not any perform flow analysis, it can't say for sure whether the parameter will have this value when the query is executed. Nevertheless, it uses the input value to come up with an estimate, which is the same as for List_orders_1: one single row. This strategy of looking at the values of the input parameters when optimising a stored procedure is known as parameter sniffing.
In the last procedure, it's all different. The input value is copied to a local variable, but when SQL Server builds the plan, it has no understanding of this and says to itself I don't know what the value of this variable will be.
...
Key Points
In this section, we have learned three very important things:
-A constant is a constant, and when a query includes a constant, SQL Server can use the value of the constant with full trust, and even take such shortcuts to not access a table at all, if it can infer from constraints that no rows will be returned.
-For a parameter, SQL Server does not know the run-time value, but it "sniffs" the input value when compiling the query.
-For a local variable, SQL Server has no idea at all of the run-time value, and applies standard assumptions. (Which the assumptions are depends on the operator and what can be deduced from the presence of unique indexes.)

And second great article Parameter Sniffing Problem and Possible Workarounds

Huge performance difference between exec of SP and running the statements of sp is solved by alter query (without any change) of the same SP

I don't know sql-server so this may be completely wrong, but in another DBMS stored procedures are compiled with the statistics that exists when the sp are created. That is, if data changes a lot the access plan compiled for the sp may be sub-optimal. This may explain why a recreate of the sp improves performance. Check if there are any utility that can recompile the sp without having to recreate it.

SQL - any performance difference using constant values vs parameters?

It is important to distinguish between parameters and variables here. Parameters are passed to procedures and functions, variables are declared.

Addressing variables, which is what the SQL in the question has, when compiling an ad-hoc batch, SQL Server compiles each statement within it's own right.
So when compiling the query with a variable it does not go back to check any assignment, so it will compile an execution plan optimised for an unknown variable.
On first run, this execution plan will be added to the plan cache, then future executions can, and will reuse this cache for all variable values.

When you pass a constant the query is compiled based on that specific value, so can create a more optimum plan, but with the added cost of recompilation.

So to specifically answer your question:

However, I seem to recall that if you use constant values in SQL statements that SQL server won't reuse the same query execution plans, or something to that effect that causes worse performance -- but is that actually true?

Yes it is true that the same plan cannot be reused for different constant values, but that does not necessarily cause worse performance. It is possible that a more appropriate plan can be used for that particular constant (e.g. choosing bookmark lookup over index scan for sparse data), and this query plan change may outweigh the cost of recompilation. So as is almost always the case regarding SQL performance questions. The answer is it depends.

For parameters, the default behaviour is that the execution plan is compiled based on when the parameter(s) used when the procedure or function is first executed.

I have answered similar questions before in much more detail with examples, that cover a lot of the above, so rather than repeat various aspects of it I will just link the questions:

Does assigning stored procedure input parameters to local variables help optimize the query?
Ensure cold cache when running query
Why is SQL Server using index scan instead of index seek when WHERE clause contains parameterized values

Between operator generating bad query plan when using parameters

The query plan is based on the parameter values when you first run the query. This is called parameter sniffing. When you add option (recompile), a new plan is generated for each execution.

A query plan is cached based on the hash of the SQL query. So there's a different cache slot for both versions of your query.

Adding option (recompile) is a good solution. You could also use:

option (optimize for (@startdate = '20130128', @enddate = '20130129'));

To generate a query plan as if those values had been passed in.

For testing, you can remove all plans from the cache with:

DBCC FREEPROCCACHE

Can I query the parameters and selected column names from a stored procedure?

The parameters should be available in the metadata tables (I seem to recall they might even be in syscolumns against the object_id of the proc). Or the info-schemas.

However, results are tricker, since SPs don't have very formalilsed output. UDFs have much stronger metadata. The best you can do with an SP (and it is still hit'n'miss) is SET FMT_ONLY ON, and execute it and hope it doesn't use any extended stored procedures...