what is the accuracy we can predict tertiary protein structure
That depends on the protein. If the primary sequence closely matches the sequence of a protein for which the structure is already resolved, then template-based methods to model 3D structure can be used (a.k.a homology modeling). These methods tend to be accurate, as assessed by template-modeling score, though crystal structure confirmation is only available for a minority of models (1%, per this 2010 paper).
For proteins without structurally-resolved homologs, ab initio folding is often used, which relies on molecular mechanics assessment of iterative peptide chain folding to find structures that minimize the Gibbs free energy. Popular software for protein molecular mechanical modeling include CHARMM and AMBER. Ab initio methods are computationally intensive and are more difficult to validate.
'why a cell can make exactly the same protein structure thousands of time using known to us physical laws, but we have to guess it using machine learning'? Why is it difficult?
It's hard to know all the cellular factors present when a particular protein is synthesized and how those factors affect the folding of the protein. What is the temperature and pH proximal to the ribosome? Are chaperone proteins involved? Is the lowest-energy structure the true structure, or does the native structure fall in a local, stable minimum with a functional potential selected by evolution? A good discussion of that last point can be found on Quora.