At what point is a new soul created according to the Catholic Church? It seems clear that Catholic Church rejected Origen's claim that souls were created and existed before conception and birth.

Does the Church pinpoint fertilization of the egg as the moment a soul is created, or upon implantation, or once the heart starts beating, or at some other stage before birth? Or is it upon the taking of the first breath, since the Greek word pneuma ("breath") is associated with the word "soul"? Or does it happen at some other point in time?

According to the Catholic Church, when do souls start to exist?
It seems clear that Catholic Church debunked Origen's claim that souls were created and existed before conception and birth.


It is more accurate to say "rejected" than "debunked" but there is substantial theological support to that rejection(cf. below).  Certainly the soul is there before birth according to current teaching of the RCC.   Current teaching has had the benefit of 1500+ years of theological development since Origen fell out of favor, and points to the soul being created "at the time of conception" bearing in mind that the unity of body and soul provides the complementary teaching that at conception (the beginning of the body) one finds the beginning of the soul.  

Humans don't create souls, God does.  CCC 366 (below) points to that fusion as  happening immediately and being done by God.  

The Catechism of the Catholic Church (Article 2270, in English): 


  2270 Human life must be respected and protected absolutely from the moment of conception.  
  
  From the first moment of his existence, a human being must be recognized as having the rights of a person - among which is the inviolable right of every innocent being to life. 
  
  Before I formed you in the womb I knew you, and before you were born I consecrated you.


The italicized portion comes from Jeremiah 1:5.  

The above extract is a subset of a longer discourse beginning in article 2258 about life and not taking innocent life, per the Fifth commandment, which then goes to abortion and euthanasia and suicide and more.  The "before I formed you in the womb" stands out, when combined with earlier articles in the Catechism that presents the soul: 


  365 The unity of soul and body is so profound that one has to consider the soul to be the "form" of the body i.e., it is because of its spiritual soul that the body made of matter becomes a living, human body; spirit and matter, in man, are not two natures united, but rather their union forms a single nature. 
  
  366 The Church teaches that every spiritual soul is created immediately by God - it is not "produced" by the parents - and also that it is immortal: it does not perish when it separates from the body at death, and it will be reunited with the body at the final Resurrection.


From that combination, and Jeremiah, the meaning comes across as either that 


the soul was known to God before conception, or
that the soul and physical being/body are joined at the time of conception

Based on the unity of body and soul as a concrete teaching of the church, the latter articles are the more explicit.  The passage in Jeremiah can be understood as "formed in the womb" summarizing the entire process of gestation before birth, which marries up with the latter conclusion just fine.      


Final Answer: at time of conception but it takes some putting together of puzzle pieces to get there.   

Caveat

At what level of teaching can one place this conclusion, or the elements of official teaching that inform this conclusion?   


The CCC notes DS as a source, which refers to Ludwig Ott's seminal
20th century work.  This source was cited in footnote 234 in CCC 366, as was the Council if Vienne of 1312 which addressed a variety of issues.   

The relevant pronouncement from the Council of Vienne:      


  In order that all may know the truth of the faith in its purity and all error may be excluded, we define that anyone who presumes henceforth to assert defend or hold stubbornly that the rational or intellectual soul is not the form of the human body of itself and essentially, is to be considered a heretic.  


The English translation of Ott's work was found to be without significant error.  {Nihil Obstat Jeremiah J. O'Sullivan, D.O. Censor Deputatus. Imprimatur: ~ Cornelius, Ep. Corgagiensis et Ap. Adm. Rossensis. 7 October, 1954.}  The level of teaching presented in that tome of Catholic Doctrine was Sententia certa which fits into the teaching heirarchy (from strongest to weakest) as follows ...      
Heirarchy of teachings

De fide
Fides ecclesiastica
Sententia fidei proxima
Sententia certa
Sententia communis
Sententia probabilis  

You are invited to look up those terms if you want to know their precise meaning.  I did not find a Sententia fidei proxima match with CCC 366 (to answer @Nathaniel's comment).  
Humani Generis reconfirms the Council of Vienne

When the Papal Encyclical Humani Generis (article 36) declares that the Catholic faith obliges us to hold that souls are immediately created by God it reasserts a centuries old teaching.  I am wary of taking that statement out of context and asserting that this statement moves the teaching higher up the ladder (presented above) so I make no such assertion (given that I have already been falsely accused by one user here of declaring a dogma).  The CCC 366 is content to state that point in official teaching without further exposition, nor a further definition, semantically, of what "immediately" means here. (To answer @PeterTurner's comment).  The church writes in its own style, and from within its own context.        


  In Roman Catholic theology, Sententia certa refers to teachings without final approval but clearly deduced from revelation.  These are below the Sententia fidei proxima level, but above Sententia communis.  



Theological support for this position ... in general

It is Theologically Certain that souls are created at the moment they are joined with the body.
That is the argument made by Fr. John A. Hardon, S.J., as he makes the case, or at least attempt so, for promoting this position to the next echelon - Sententia fidei proxima.  Whether or not that appeal was successful is beyond the scope of this question, since the Catechism uses the term without further exposition.  


  Positively stated, it is De Fide ex Jugi that human souls are
  immediately created by God.  Apart from the constant position of the
  Church since the time of St. Thomas, we have the recent declaration of
  Pius XII in Humani Generis to be quoted in the body of the proof. It
  is Theologically Certain that souls are created at the moment they are
  joined with the body. {SNIP}   


Theological Support ... in detail

based on Immediate Creation of the Soul by God: 
Source is Fr. John A. Hardon, S.J. at the linked (exhaustive) argument.   Selected excerpts are: 


  It is De Fide Definita that spiritual substances, and therefore the soul, do not emanate from the substance of God.  This from the condemnation of Pantheism in the Vatican Council, DB 1804.   
  
  Though not defined, it is De Fide ex Jugi Magisterio that material Traducianism is wrong. Thus St. Thomas' statement, quoted above, indicates the ordinary teaching of the Church.  
  
  Positively stated, it is De Fide ex Jugi that human souls are immediately created by God. Apart from the constant position of the Church since the time of St. Thomas, we have the recent declaration of Pius XII in Humani Generis to be quoted in the body of the proof.
  It is Theologically Certain that souls are created at the moment they are joined with the body.
  {SNIP}
  Part Three: “The Human Soul is Immediately Created by God Alone.”
  Ecclesiastical Documents
  
  The Vatican Council defined against the pantheists that, “If anyone
  says that finite things, both corporeal and spiritual, or at least
  spiritual, emanated from the divine substance...Let him be anathemas
  DB 1801. Thus it is defined that however the soul originates, it is
  not by way of emanation from the deity.
  
  Benedict XII in 1341 condemned the errors of certain Orientals, on the
  occasion of prospects for reuniting the schismatic Armenians with
  Rome. "A certain teacher,” wrote the pope, "again introduced the
  teaching that the human soul of a son is propagated from the soul of
  his father, as his body is from the body of his father. He taught also
  that angels are propagated one from another. He gave as his reason for
  this that, since a rational existing human soul, and an angel existing
  in an intellectual nature are a kind of spiritual light, they
  propagate other spiritual lights from themselves" DB 533. The Armenian
  who held this doctrine was named Mechitriz, which means “paraclete."
  By condemning Mechitriz, Benedict XI condemned generationism, even of
  a spiritual kind, since the erroneous teaching referred to both human
  souls and the angels.  


{my note here: the following point really stands out, since the Catholics believe that Jesus is both divine and human - his mother was wholly human}
**> the Bull Sollicitudo omnium ecclesiarum of Alexander VII (1661), the


  Pope declared that, "It is an ancient belief of the faithful of Christ
  regarding His most blessed Mother the Virgin Mary holding that her
  soul, in the first moment of its creation and infusion into the body,
  by a special grace and privilege of God, in view of the merits of
  Jesus Christ her Son, Redeemer of the human race, was preserved free
  from the stain of original sin” DB 1100.** Two centuries later, Pius IX
  adopted the statement of Alexander VII almost verbally in his
  definition of the Immaculate Conception. Alexander VII, therefore,
  pre-supposed that human souls are created and infused into the body by
  a special creative act of God.  
  
  Pius XIII, in the Encyclical Humani Generis, when speaking on the
  subject of evolution of the human body, declared expressly that “the
  Catholic faith obliges us to hold that the human soul is immediately.
  created by God (animas a Deo immediate creari, Catholic fides nos
  retinere jubet)” - Weston translation, paragraph 37. Though speaking
  in context of the evolution of the first man, the incisum on the
  creation of the soul is of general import, as indicated by the plural
  collective animas creari.
  
  Sacred Scripture
  
  There is no direct, conclusive argument from Scripture proving that
  human souls are directly created by God.  True the soul of Adam is said
  to have been created by God (Genesis 2:7), but Scriptures are silent
  about the precise origin of souls after Adam.  A suasive argument can
  be deduced from such texts as “The dust returns to the earth from
  whence it came, and the spirit returns to God, who gave it”
  Ecclesiastes 12:7; and the words of the mother of the Maccabees to her
  sons, “I neither gave you breath, nor soul, nor life but the Creator of the world" II Maccabees 7:22. Both these texts show that God somehow specially produced the human soul, but not necessarily by immediate creation, which must be proved against spiritual generationism.  
  
  The best argument from Scripture is indirect, reasoning from the different passages which say or describe the soul as spiritual and immortal. Then by analyzing the nature of spirituality or immortality we conclude that only God could produce a spirit.  
  
  Patristic Evidence
  
  As noted before, the Patristic position on creationism labors under
  special difficulties because of the ambiguous (or better, hesitating)
  attitude of St. Augustine who favored immediate creation but feared
  its consequences in the Pelagian crisis. However there is a definite
  Patristic tradition which should not be minimized.
  
  As regards the Greek Fathers, it is commonly recognized that they had
  no sympathy with generationism but, as a group, professed immediate
  creation of the soul by God.
  
  The Latin Fathers before Augustine are most significant here; and
  among them we find, e.g., St. Hilary denying that the soul is
  propagated by the parents.(RJ 875); Lactantius declaring that, "This
  question may also be asked: whether the soul comes from the father
  rather than the mother, or whether it is generated by both. But I am
  justly delivered from this uncertainty, since none of these three is
  true...The power of giving origin to souls belongs to the one and only
  God" De Opificio Dei, 79.
  
  Theological Reason
  
  There are two distinct propositions that may be defended by
  theological reason: 1) that human souls are immediately created by God
  alone, and 2) that they are created at the time of their union with
  the body.
  
  The first assertum, which is properly our thesis, builds on the datum
  of revelation (also proveable by reason) that the soul is a spiritual
  substance. Given a substance which is spiritual, and therefore
  incomposite or integrally simple by nature, it cannot be divided to
  give "part of itself" to someone else, as Traducianism and even
  spiritual Gene rationism logically require.
  
  The second assertum answers the further question of when the soul is
  created, saying this takes place at the time of its infusion into the
  body. This follows logically on the defintion of the Council of Vienne
  (1311-1312), which declared:
  
  "We condemn as erroneous and opposed to Catholic truth every doctrine
  and opinion that rashly asserts that the substance of the rational,
  intellectual soul is not truly and by its own nature the form of the
  human body" DB 481.
  
  If, therefore, it is defined that the rational soul is truly, per se,
  and essentially the form of the body, then it must be created at the
  time at which it is joined with the body. Otherwise it could not be
  said that the soul (created by God) is essentially the form of the
  body; since then we should have either a pre-existing soul (minus a
  body) or an informed human body (minus a soul) - both of which are
  theologically untenable.




Postscript

When you work with concepts and doctrines about God being omnipresent, and thus unbound by time, the whole idea of "before" for God loses meaning.  This could lead to an understanding that God knowing you is a condition being unbounded by time at all.  While it is an interesting line of inquiry, it does not address your question.  God's creation of Adam, from the dirt as described in Genesis, and then Adam coming to life, and Adam having a soul, provides a useful template (or even a precedent) for the unification of body and soul at the time of creation-conception.