Given a message and signature, find a public key that makes the signature valid (ECDSA)
Yes. We can easily generate the malicious public key as in DSS case.
The following attack was proposed in Section 4.5 of Blake-Wilson and Menezes: Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol (PKC 1999).

Let $(G,q,n,P)$ be the ECDSA parameters, where $n$ is the order of the group $G$ over the elliptic curve and $P$ is a generator of $G$.

Let $P_1 = d_1 P$ be the public key, let $M_1$ be the message, and let $S_1 = (s_1, r_1)$ be the signature as you noted.

Since $S_1$ is a valid signature under the public key $P_1$, it satisfies the following equaitons.
$$ s_1 k_1 \equiv e_1 + d_1 r_1 \pmod{n},$$
where $e_1$ is a digest of the message $M_1$, and $r_1 \in \mathbb{Z}_n$ is a $x$-coordinate of $k_1 P$ modulo $n$.

How to construct a malicious public key

Let $M_2$ be the target message.
We now virtually compute a malicious secret key $d_2$ as
$$ d_2 = r_1^{-1} (s_1 k_1 - e_2) \bmod{n}, $$
where $e_2$ is a digest of the message $M_2$.
We then compute a malicious public key $P_2 = d_2 P$, which is 
$$ r_1^{-1} (s_1 k_1 - e_2) P = r_1^{-1} (e_1 + d_1 r_1 - e_2) P = r_1^{-1}(e_1 - e_2)P + P_1$$.

Validity of the public key $P_2$.

The public key $P_2$ makes the message $M_2$ and the signature $S_1 = (s_1, r_1)$ valid.
Let us verify the validity of them.


$r_1$ and $s_1$ is in the range $[1,n-1]$, because the signature $S_1$ is valid.
Let $X = u_1 P + u_2 P_2$, where $u_1 = e_2 s_1^{-1} \bmod{n}$ and $u_2 = r_1 s_1^{-1} \bmod{n}$.
By the construction of $P_2$, we have $X = (u_1 + u_2 d_2) P = s_1^{-1} (e_2 + r_1 d_2) P = s_1^{-1} (s_1 k_1) P = k_1 P$.
Therefore, $r_1$ is the $x$-coordinate of $X$.


How to prevent this attack

It is easy to prevent this attack.
We just use a digest $e' = \mathrm{Hash}(pk,M)$ instead of $e = \mathrm{Hash}(M)$.