In what direction is positive work done under a gravitational force, and what justifies the relation between work, potential and kinetic energy?

It is important to understand who is doing the work. In general, the work done by a force is positive, if the displacement of object on which the force is acting is positive with regard to said force.

Take your example of a falling particle of mass $m$ falling toward a larger object of mass $M$. Let $textbf{r}$ be the radial vector connecting their center of masses, with the origin being at the C.O.M. of the larger mass. The mass $m$ experiences a force $$textbf{F}_G = -G frac{mM}{|textbf{r}|^3} textbf{r}$$ due to the gravitational field of mass $M$. The work done by this field in taking $m$ from $textbf{r}_1$ to $textbf{r}_2$ is given by integrating this force over that interval:

$$text{W}_G = -G m M, int_{textbf{r}_1}^{textbf{r}_2}frac{textbf{r} cdot dtextbf{r}}{|textbf{r}|^3} = -G m M, int_{r_1}^{r_2}frac{1}{r^2}, dr = Gm Mleft(frac{1}{r_2} - frac{1}{r_1}right).$$ Notice that as the object is falling toward $M$, $r_2 < r_1,$ so this work done is positive. This makes sense, since $m$ is moving in the same direction as the field of $M$.

Now, consider an external force $textbf{F}_{text{ext}}$ acting on $m$ such that it is always equal and opposite to $textbf{F}_G$: $$textbf{F}_{text{ext}} = -textbf{F}_G$$ In this case, $m$ will move toward $M$ without acceleration. If you calculated the work done by this external force on $m$, you would get $text{W}_{text{ext}} = - text{W}_G$; i.e. the work done is negative. This also makes sense, since $m$ is moving opposite in relation to the external force.

This is incidentally also how the potential of a field is defined: It is the work done by an external agency in moving a unit mass from infinity to a point. For a gravitational field, this potential is thus negative, as our example showed. The $net$ work done on the object, that is by both forces, is zero in this example, since both the field as well as the external force did equal amounts of work opposite to each other.

As for the work-energy relation you mention, it follows readily if you accept the definition of energy as the capacity for doing work, that is to say the work done on an object gets converted into energy: $$Delta W = Delta T + Delta U.$$ This relation holds for all agents doing path-independent work on the object once you make sure that you use the $Delta U$ corresponding to the force under consideration. I invite you to verify this relationship for the examples above.

In Newtonian mechanics, energy arises from the line integral of the second law along the object's path:

$Sigma_ioverrightarrow F_i = moverrightarrow a = mfrac{doverrightarrow v}{dt} int (Sigma_ioverrightarrow F_i) cdot doverrightarrow r = int m frac{doverrightarrow v}{dt} cdot doverrightarrow r Sigma_i int overrightarrow F_i cdot doverrightarrow r = mint doverrightarrow v cdot frac{doverrightarrow r}{dt}$

That last step on the right-hand side is a key concept: we can move the $dt$ from $doverrightarrow v$ to $doverrightarrow r$, because the change in velocity and change in position happen during the same time interval -- all three differentials correspond to the same little piece of the path. Also, on the left-hand side, we simply define the work done by a force as $intoverrightarrow Fcdot doverrightarrow r$, so we have:

$Sigma_i W_i = mint doverrightarrow vcdot overrightarrow v$

Now the other key point: $doverrightarrow v cdot overrightarrow v$ is the differential of $frac12 overrightarrow v cdot overrightarrow v = frac12 v^2$. So

$Sigma_i W_i = mDelta(frac12 v^2)$

Likewise, we define kinetic energy as $K = frac12 mv^2$. That makes intuitive sense: the more massive an object is and the faster it's moving, the more motion energy it has.

$Sigma_i W_i = Delta K$

That's the work-energy theorem: the sum of the works done by all forces gives the change in kinetic energy.

Now, for a given force, that line integral will in general depend on the path the object takes. But oddly, it turns out that the fundamental forces of nature, such as gravity and the electric force, do the same amount of work for any path between two given points. So we don't need to do the integral every time. We just need a formula for the work they will do, in terms of the two endpoints.

$W = W(overrightarrow r_i, overrightarrow r_f)$ for a path-independent force

But we can also think of that work as the kinetic energy the object stands to gain by moving from $overrightarrow r_i$ to $overrightarrow r_f$. So we call that the potential energy of $overrightarrow r_i$ relative to $overrightarrow r_f$:

$U(overrightarrow r_i) - U(overrightarrow r_f) = W(overrightarrow r_i, overrightarrow r_f) U(overrightarrow r_f) - U(overrightarrow r_i) = -W(overrightarrow r_i, overrightarrow r_f) Delta U = -W$

So the potential energy difference has the opposite of the kinetic energy difference: for a path-independent force, the object loses the same amount of potential as it gains kinetic, by virtue of our definition. Which means that if you add the potential and kinetic just due to that force, they remain the same.

Therefore, you can take the work-energy theorem above, and replace the work terms in the sum by potential energy changes - but only for those forces that have potential energy, ie. path-independent forces:

$Sigma_i W_i = Delta K Sigma_{path-independent}(-Delta U_i) + Sigma_{path-dependent}W_i = Delta K$

Now, if all forces do path-independent work, we have:

$Sigma_i(-Delta U_i) = Delta K -Delta U_{total} = Delta K Delta U + Delta K = 0 Delta(U + K) = 0$

That is, total mechanical energy is conserved. Therefore, we call those path-independent forces conservative forces.

So that's mechanical energy in a nutshell. But as to your problem, it actually goes back to that definition of work, because it's the integral of the dot product. At all points along your path, gravity is pointing toward the second object's COM, and so is the displacement of the first object. Since those two vectors have the same direction, their dot product is positive, not negative. So your work will come out positive.

The intuition behind the work formula is that, when you push an object and it moves the direction you're pushing it, you are contributing to the accomplished motion, so you're doing positive work. But if someone else pushes harder, and it moves against your push, you're hindering the process, hence doing negative work. The harder you pushed and the further it moved, the more work you did.

So, like you said, mathematically, energy is just a set of definitions on top of the second law - but those definitions match the intuitive understanding of the terms, and the math gives us shortcuts to solving problems.

EDIT: Note I said it was "odd" that the fundamental forces of nature are path-independent, ie. conservative. But, in retrospect, that fact suggests that energy is actually a very natural concept in physics, perhaps more so than force. The derivation from force is slightly awkward, but energy conservation is a much more universal principle (even if it's not quite as strict in modern physics).