This is a really interesting question. According to The Oxford Dictionary of English Proverbs (Clarendon Press, 1970), the proverb may come from the Latin expression Usus promptum facit. An earlier English correlate was Use makes perfectness. The earliest citation that comes close to Practice makes perfect is the following sentence, from Arte of Rhetoric (T. Wilson, 1560): "Eloquence was used, and through practice made perfect."
I think that quotation sheds light on the structure of Practice makes perfect. "Eloquence was made perfect through practice." That's in the passive voice. The normal active correlate would be "Someone made eloquence perfect through practice," but it could also be interpreted as an instrumental passive, such that the active correlate would be: "Practice made eloquence perfect."
In Practice makes perfect, we have the present tense. Transformed into the passive, the sentence could be rephrased as "Anything perfectable is made perfect through practice." That would make the omitted direct object in the active voice a phrase like "anything perfectable," viz.: Practice makes [anything perfectable] perfect. The "anything perfectable" part naturally falls away.
Alternatively, one could analyze "makes perfect" as meaning "perfects," such that Practice makes perfect means, simply, Practice perfects.
