I'm assuming your question is about how proteins have evolved from their earliest forms into those that are found today. As has been stated in the comments, changes in protein primary structure occur as a consequence of changes in the nucleotide sequences of the genes that encode them. Such changes may be caused by mutation or recombination.
Mutations are changes in the nucleotide sequence that can be spontaneous, caused by errors in replication or DNA repair, or induced by mutagens such as radiation or chemicals. Recombination (non-meiotic) is the breaking and joining of different DNA strand, producing new strands with new combinations of alleles. Both these processes could result in changes in the amino acid sequence of proteins, affecting its tertiary structure and thus function. Through these processes, evolution has selected for nucleotide sequences carrying mutations that have caused beneficial changes in protein structure.
As for your follow-ups, I don't think there is an absolute answer. What is certain is that genetic complexity has increased through time, so the earliest genes that were part of a system in which a genetic code could be translated into protein are likely to have been both fewer and shorter.