Determine a basis $B$ of $mathbb{R}^4$ and a basis $C$ of $mathbb{R}^5$

So do we have to write each column of $A$ as a linear combination of $C$ and the corresponding coefficients have to satisfy the desired form that $M$ will have?

If I understand you correctly, then yes. More explicitly, if $B={b_1,dots,b_4}$ and $C={c_1,dots, c_5}$ are bases of of $mathbb R^4$ and $mathbb R^5$, respectively, and $M^B_C(A)$ looks like

$$M^B_C(A)=begin{pmatrix}alpha_1&beta_1&gamma_1&delta_1\ alpha_2&beta_2&gamma_2&delta_2\ alpha_3&beta_3&gamma_3&delta_3\ alpha_4&beta_4&gamma_4&delta_4\ alpha_5&beta_5&gamma_5&delta_5end{pmatrix},$$

then that means that $b_1$ is mapped to $alpha_1 c_1+dots+alpha_5c_5$, while $b_2$ is mapped to $beta_1c_1+dots+beta_5c_5$, and so on. Now you want it to look like

$$M_C^B(A)=begin{pmatrix}1&0&0&0\ 0&1&0&0\ 0&0&1&0\ 0&0&0&1\ 0&0&0&0end{pmatrix}.$$

So $b_1$ should be mapped to $c_1$, $b_2$ to $c_2$, and so on. The easiest way to find such bases would be to just take the standard base as $B$. Then look at the vector to which $b_i$ is mapped and choose that as $c_i$. Then choose some additional vector as $c_5$ which completes the base.