Here I propose a proof showing that the conjecture above holds at least for one left-invariant mean.
Denote by $L$ and $R$ respectively the set of all left-, right-invariant means on $G$. Denote by $P$ the set of all finitely additive probability measures on $G$.
Theorem: There is $\lambda\in L$ such that the functional $\mu\in P\rightarrow\int\int f(xy)d\mu(x)d\lambda(y)$ attains its maximum in some $\rho\in R$.
Proof: By Theorem 3 (and discussion below) of Heath-Sudderth, On a theorem of De Finetti, oddsmaking and game theory, Ann. Math. Stat. (1972), vol. 43, No. 6, 2072-2077, the following equality holds:
$$
\inf_{\nu\in P}\sup_{\mu\in P}\int\int f(xy)d\mu(x)d\nu(y)=\sup_{\mu\in P}\inf_{\nu\in P}\int\int f(xy)d\mu(x)d\nu(y)
$$
Denote by $L$ this common value. Fix $\epsilon_1,\epsilon_2>0$. The RHS tells us that
(1) there is $\mu\in P$ such that $\int f(xy)d\mu(x)\geq L-\epsilon_1$, for all $y\in G$.
The LHS tells us that
(2) there is $\nu\in P$ such that $\sup_{\mu\in P}\int\int f(xy)d\mu(x)d\nu(y)\leq L+\epsilon_2$.
Let $F_n$ be a right-Folner sequence for $G$ and define $\nu_n(A)=\frac{1}{|F_n|}\sum_{g\in F_n}\nu(gA)$. It is straightforward to prove that $\nu_n$ still verifies property 2 and so does any weak* limit, which is a left-invariant mean. Denote by $\nu_{\epsilon_2}$ this left-invariant mean. Now, let $\epsilon_2$ go to zero and let $\lambda$ be any weak*-limit of the net $\nu_{\epsilon_2}$. Hence $\lambda\in L$ and it verifies the following property
(2 bis) $\int\int f(xy)d\mu(x)d\lambda(y)\leq L$, for all $\mu\in P$.
Now, let us get back to property 1, and uniformize $\mu$ as above but using a left-Folner sequence. In this way, any weak*-limit is right-invariant and still verifies property 1. So, we have gotten the following property:
(1 bis) There is $\rho_{\epsilon_1}\in R$ such that $\int f(xy)d\rho_\epsilon(x)\geq L-\varepsilon_1$ (contantly in $y$).
Now, the set of real numbers of the shape $\int f(xy)d\rho(x)$, for some $\rho\in R$, is compact and so, by 1 bis, there is $\rho\in R$ such that $\int f(xy)d\rho(x)=L$. Now, using 2 bis, it follows that our functional, for that particular $\lambda\in L$, attains indeed its maximum in $\rho\in R$, as claimed.