I assume that your question concerns convex functions only; without convexity much of it would be false.
Question 2: strictly speaking, being Lipschitz smooth ($C^{1,1}$) does not imply $\nabla^2 f$ exists. But the statement is true if we interpret $\nabla^2 f\preceq LI$ as holding almost everywhere. Indeed, $\nabla^2 f$ is a positive semidefinite matrix, so having $\nabla^2 f\preceq LI$ a.e. is equivalent to $\nabla^2 f\in L^\infty$. And it is well known that having $L^\infty$ derivative is equivalent to being Lipschitz; thus $$\nabla^2 f\in L^\infty \iff \nabla f\in C^{0,1} \iff f\in C^{1,1}$$
Question 3: You misremembered. The correct inequality characterizing $\alpha$-strong convexity is
$$f(x+y) \ge f(x) + y^\top\nabla f(x) + \frac{\alpha}{2} \| x - y \|^2 \tag{1}$$
Indeed, (1) is equivalent to saying that the function $g(x)=f(x)-\frac{\alpha}{2} \| x \|^2$ is convex. The latter is equivalent to $\nabla^2 g\succeq 0$, which is $\nabla^2 f\succeq \alpha\, I$.
Question 4. Yes, there is a direct and important relation: a function is strongly convex if and only if its convex conjugate (a.k.a. Legendre-Fenchel transform) is Lipschitz smooth. Indeed, the gradients maps are inverses of each other, which implies that the Hessian of convex conjugate of $f$ is the inverse of the Hessian of $f$ (at an appropriate point). So, a uniform upper bound on $\nabla^2 f$ is equivalent to a uniform lower bound on $\nabla^2 (f^{*}) $, and vice versa. One can also argue without referring to the Hessian (which may fail to exist at some points): the Lipschitz smoothness of $f$, by your item 1, gives us at every $x_0$ a quadratic function $q$ so that $q(x_0)=f(x_0)$ and $f \le q$ everywhere. Taking convex conjugate reverses the order: $q^*\le f^*$; and this means that $f^*$ is strongly convex.
Question 1. The converse is true, but the only proof I see goes through the convex conjugate as described in Q4. Since strong convexity is characterized by the comparison property (1), taking the conjugate gives a matching characterization of Lipschitz smoothness.
Reference: Chapter 5 of Convex functions by Jonathan M. Borwein and Jon D. Vanderwerff.
This is true. Notice that taking the dual reverses inequalities: $f\ge g$ implies $f^*\le g^*$.
Fix $x_0$ and let $y_0=\nabla f(x_0)$. Define
$$g(x) = f(x_0) + y_0^T (x-x_0) + \frac{1}{2}\|x-x_0\|^2 \tag{1}$$
This is a convex quadratic function of $x$. Its dual is
$$
g^*(y) = g(y_0)+x_0^T(y-y_0)+ \frac{1}{2}\|y-y_0\|^2 \tag{2}
$$
(The derivation of $(2)$ is standard; included below for completeness.)
So, strong convexity of $f$ at $x_0$, expressed as $f\ge g$, implies $f^*\le g^*$, which is the strong smoothness of $f^*$ at $y_0$. Similarly the other way around.
Proof of $(2)$
Since $\nabla g(x) = x-x_0+y_0$, it follows that $\max_x (y^T x - g(x))$ is attained when $x-x_0+y_0=y$, which implies
$$\begin{split}
g^*(y) &= y^T(y-y_0+x_0) - \left(f(x_0) + y_0^T (y-y_0) + \frac{1}{2}\|y-y_0\|^2 \right) \\
&= (y-y_0)^T(y-y_0) +y^Tx_0 - f(x_0) - \frac{1}{2}\|y-y_0\|^2 \\
&= -f(x_0) + y^Tx_0 + \frac{1}{2}\|y-y_0\|^2
\end{split}$$
Since $g^*(y_0)=-f(x_0)+y_0^Tx_0$, the latter formula can be rewritten as $(2)$.
Best Answer
In general, these are computationally difficult problems. For example, "merely" deciding convexity of a multivariate polynomial of degree 4 (or higher even degree) is strongly NP-hard, i.e. unless P=NP, there is no polynomial time algorithm or pseudo-polynomial time algorithm for this problem. Also deciding strict convexity and strong convexity of polynomials of even degree of four or higher is NP-hard. These results are recently proved in https://arxiv.org/pdf/1012.1908.pdf
On the other hand, many convex functions that we encounter in practice have special structures, e.g., formed from simpler convex functions that we know their smoothness or convexity properties. Then, there is more hope to figure out specialized methods for your questions.