What is the basis of Christian belief that criminals should be punished on Earth? Do Christians believe that criminals should be punished on Earth by state authorities? 

If so, why are they not satisfied with the promised divine punishment in afterlife?
From the Catechism of the Catholic Church:


  1898    Every human community needs an authority to govern it. (Cf. Leo XIII, Immortale Dei; Diuturnum illud.) The
  foundation of such authority lies in human nature. It is necessary for
  the unity of the state. Its role is to ensure as far as possible the
  common good of the society. 1899    The authority required by the
  moral order derives from God: 
  
  
    “Let every person be subject to the governing authorities. For there
    is no authority except from God, and those that exist have been
    instituted by God. Therefore he who resists the authorities resists
    what God has appointed, and those who resist will incur judgment.”  Rom 13:1-2; cf. 1 Pet 2:13-17.
  


and here


  1909    Finally, the common good requires peace, that is, the
  stability and security of a just order. It presupposes that authority
  should ensure by morally acceptable means the security of society and
  its members. It is the basis of the right to legitimate personal and
  collective defence. 1910    Each human community possesses a common
  good which permits it to be recognized as such; it is in the political
  community that its most complete realization is found. It is the role
  of the state to defend and promote the common good of civil society,
  its citizens, and intermediate bodies.


I believe that The Fourth Commandment "Honor thy Father and Mother" can be extrapolated to Honor authority.

From Wikipedia on the Fourth Commandment


  Thus, the fourth commandment's responsibilities extend to the greater
  society and requires respect for "legitimate social authorities". The
  Catechism specifies "duties of citizens and nations", which Kreeft
  summarizes as: "Obedience and honor" to "all who for our good have
  received authority in society from God". "Payment of taxes, exercising
  the right to vote and defending one's country". "An obligation to be
  vigilant and critical", which requires citizens to criticize that
  which harms human dignity and the community. "A duty to disobey" civil
  authorities and directives that are contrary to the moral order. "To
  practice charity", which is a "necessity for any working family or
  society"; it is the "greatest social commandment" and requires people
  to love God and neighbor. "To welcome the foreigner" who is in need of
  security and livelihood that cannot be found in his own country. "An
  obligation for rich nations to help poor nations", especially in times
  of "immediate need". "An expectation for families to help other
  families".[55][64]


It is not a dissatisfaction with the promised divine judgement, it is the governing authority's role from God to "ensure as far as possible the common good of the society."