The (exact mathematical) treatment of physical notions may depend on the particular theory through which we analyze them. If we look at notions in one theory and carry over this notion to a different theory, contradictions and paradoxa may result.
It looks like the problem here comes up by confusing notions from special relativity (SR) with notions from (GR).
To begin with: Two different points on a curved manifold do not allow a meaningful definition of velocity. We may, of course, define a notion of distance, for example by defining it as the minimum of the lengths of all curves connecting the two points. For defining velocity we need some notion of time or space-time or motion, which we do not have in a generic curved manifold.
The clarification given in the comment and in particular the cited lecture notes, are helpful, since they fill in some missing parts of the question. I see the followin approaches for resolving the paradox.
No clear definitions: The lecture notes claim that no "notion of velocity" is well-defined but they do not give a clear intuition of which properties a notion should have to qualify as "velocity". Thus, they are making an empty statement.
Misunderstanding 1: Lack of context: Between two points there never is a notion of velocity, independently of the nature of the manifold. What the lecture notes actually mean (but not say) is: We look at two particles (not: points) moving along geodesics in a space-time manifold.
Misunderstanding 2: Lack of criteria for "velocity": Between two particles moving on geodesics we now can attempt to define various concepts and the question then can be asked if they rightfully should be called "velocity" or not. I could, for example, study Doppler shift. I could, for example, send a photon from object $A$ to object $B$ and there have it reflected to $A$ and then divide the time measured in $A$ by some textbook value of speed of light and call the result "distance". Then I could measure "distance" in every "second" (as determined by my clock in $A$) and use the results to obtain another value which I could then call "velocity". I even can define operations to obtain "acceleration". The question is just if this experiment provides me with read-outs which I want to call "velocity" in my theory. So I can, of course, call what my Doppler formula or my other experiments provide, a "velocity". Depending on how I define this "velocity" I will get different and probably obscure results which might contradict my intuitive notion of what I expect from a velocity.
Misunderstanding 3: Confusing SR and GR: The lecture notes then proceed with "implies that some galaxies are receding faster than light, in apparent contradiction with relativity". I have several doubts regarding this sentence. First of all I am never shocked by contradictions between physical models. We have such contradictions all the time (for example between orthodox quantum mechanics and locality, between galaxy rotations curves and general relativity, and many more). Second there is no contradiction. Relative velocities of particles higher than the speed of light in vacuum only are a problem in special relativity. The setting given in the lecture notes (manifolds, parallel transport etc) indicate a setting of general relativity, where this does not pose a problem.
Cosmologic phenomena: In fact, some general relativistic space-times do show interesting phenomena. First of all: The time which passes between two events in space-time depends on the path the measuring clock travels when connecting these two events. So we could also claim: "This is no notion of time". Second: There are some objects which, according to measurements and models, recede from us with a higher "velocity" than the speed of light (due to expansion of space). It is a matter of debate and taste, if we call this "velocity" or "redshift Doppler factor". Third: Since these objects recede from us faster than light, also the experiment suggested above to measure distance or velocity or whatever fails, since photons we send out from earth will never reach these objects (and we only can look into their past until such a moment that we lose them out of sight). But Doppler shift is one possibility to attempt to define such a thing like velocity.
Update for the added question "Why does Carroll say that there is no such thing as velocity when you defined it here?". I have not checked the line of reasoning of Carroll and would appreciate a hint to which page you are referring to.
That said: I would distinguish the conceptual layers of physics and mathematics.
In physics, I can define all kinds of experiments and call the result "velocity". If it is distance divided by time it is most close to the naive definition of velocity. If it is Doppler factor and turns out to be larger than $c$ then one might be a bit more reluctant to call the corresponding value "velocity". However, one could also take a more rigid approach: We know that there is no such thing like separate differences in time values and in location values, so this entire business of velocities does not exist if we are beyond Newtonian physics (and discard special relativity as being a falsified model and mere approximation to gravity-free low energy situations).
In mathematics, we work inside of a specific formal model. In this model I can have formal proofs of non-existence for formally specified objects, such as for There is no real value $r$ such that $r^2 = -1$. An informal reasoning as given in https://physics.stackexchange.com/a/497610/139287 is atypical for how mathematics works, since it comprises no formal reasoning. Moreover, there is a well known method to solve such situations. for the given example, we extend the real numbers into the complex number field. Similarly, we could extend the notion of a manifold with tangent vectors into a notion of a manifold with tangent vectors where I can compare vectors residing in different tangent spaces. Such methods are known in several different forms (see Levi-Civita connection, parallel transport, covariant derivative, vector bundle etc.) Again the question is whether I am fine to call the resulting object a "velocity" or whatever.
Going back to the original cosmological question: It is pretty much standard to define something as peculiar velocity (with respect to the so-called comoving coordinates) and this also can be taken for reasoning about Doppler shifts, as is regularly done in astronomy. Of course, there can be reasons why one would not like to call this "velocity".
Unfortunately, many (particularly physical) texts do not distinguish clearly the different levels of reasoning and of forming notions. However, it helps cutting down on the number of pages a student has to digest...
http://www.physics.ucc.ie/apeer/PY4112/Curvature.pdf
– gyzgyz123 Aug 19 '19 at 10:25