How to obtain a good execution plan for (LIKE @p) when the pattern is of the form 'prefix%'
I would like SQL Server to discover at execution time the relevant
  range of the index to scan and only scan that range.


This is exactly the plan I get.

CREATE TABLE T(Columns VARCHAR(50), 
               Col VARCHAR(50), 
               INDEX IX(Col, Columns));

DECLARE @p0 VARCHAR(50) = 'foobar%'

SELECT Columns
FROM T
WHERE Col LIKE @p0 ESCAPE '~'




See Dynamic Seeks and Hidden Implicit Conversions for more about this. 

Check that the index is indeed covering and that the datatype of the parameter is correct for the column definition (i.e. if the column is varchar and the parameter is nvarchar this can cause a scan).