funs = Function[{expr}, Extract[expr, {1, #}, HoldForm] & /@ Range[Length[expr[[1]] ] ] ]@ Hold[ {x^(4/3), x*E^Sqrt[8 Log2[5/2]*Log2[x]], x^2, x^(3/2), x*Log2[x]^2} ]; LogPlot[funs // ReleaseHold // Evaluate, {x, 10, 1000000}, PlotLegends -> LineLegend[TraditionalForm /@ funs, LegendMarkers -> Automatic] ] 

I feel the following satisfies your three requirements of 1) having the labels unevaluated, 2) logs in TraditionalForm, and 3) functions specified only once:

funs = Function[{expr}, Extract[expr, {1, #}, HoldForm] & /@ Range[Length[expr[[1]] ] ] ]@ Hold[ {x^(4/3), x*E^Sqrt[8 Log2[5/2]*Log2[x]], x^2, x^(3/2), x*Log2[x]^2} ]; LogPlot[funs // ReleaseHold // Evaluate, {x, 10, 1000000}, PlotLegends -> LineLegend[TraditionalForm /@ funs, LegendMarkers -> Automatic] ]