Why does the concatenation order change with a User-Defined Table Type?
The order changes because the order of the tables involved in the cross join has changed. In one plan @ValueTable is the outer (driving) table, in the other @ColumnNames is the outer table.

for each row in @ColumnNames
    for each row in @ValueTable
    concatenate the result
    //produces Forename - Ellis, Forename - Ali, Surname - Ellis, Surname - Ali, 


for each row in @ValueTable
    for each row in @ColumnNames
    concatenate the result 
    //produces "Forename - Ellis, Surname - Ellis, Forename - Ali, Surname - Ali,"


Order is never guaranteed unless specified in the query, so if consistent order is important you should add a stable order by clause defining order for both tables inside the STRING_AGG definition.

SELECT CONCAT(STRING_AGG(CONCAT([ColumnName], ' - ',  [sc].[Value]), ', ') 
                        WITHIN GROUP (ORDER BY [ColumnName],  [sc].[Value])  , ', ') -- QueryLineA
FROM        @ValueTable AS [sc]
INNER JOIN  @ColumnNames ON 1=1