What to treat as (hyper-)parameter and why I have been wondering about the differences between model paramters and model hyperparameters, as well as what their categorization means for a learning problem.
Is the distinction between model parameters and hyperparameters only about reducing the complexity of the problem or are there implications for the 'model quality' to be considered?
Let's consider an example from (1, Eq. 2.43), a linear expansion of basis functions 
$$f_\theta(x) = \sum_{m=1}^{M} \theta_m h_m(x), $$
where $h_m\:\forall m=1,...,M$ is some function of $x$, $\theta=[\theta_1,...,\theta_M]^\intercal$ is a vector of the parameters of the model and $M$ is the number of basis functions. 
In my understanding, we would consider $\theta$ to contain the parameters of the model, while $M$ is a hyperparameter.
To quote the Wikipedia article of hyperparameter that I linked above:

In machine learning, a hyperparameter is a parameter whose value is
  set before the learning process begins. By contrast, the values of
  other parameters are derived via training.

It makes sense treating the values in $\theta$ as parameters that should be learned from the data, similar to the coefficients in a linear model - it is surely far more reliable  and  specifying them manually would be quite annoying, although it's not impossible.
But what about $M$? It surely is easier to pick some integer value for it. But would it really be terrible to determine $M$ based on the data, too? Probably not, as that is what we would do if we search a grid of possible values for the best performing one. 
Let's consider the above basis expansion model and choose Gaussian kernel functions to serve as basis functions. As the Kernel itself has parameters too 
this makes the problem a bit more complicated.
$$f_\theta(x) = \sum_{m=1}^{M}\theta_m K_{\lambda_m}(\mu_m,x), $$
with $\mu_1,...,\mu_m$ being the location of the kernels and $\lambda_1,...,\lambda_m$ their scales/bandwidths.
Friedman et al. write in (1, p. 36)   

"In general we would like the data to dictate them as well. Including
  these as parameters changes the regression problem from a
  straightforward linear problem to a combinatorially hard nonlinear
  problem. In practice, shortcuts such as greedy algorithms or two stage processes are used."

I see that if we were to treat $M$, $\theta_1 ... \theta_M$, $\mu_1 ... \mu_M$ and $\lambda_1 ... \lambda_M$, as model parameters, this problem would be really complex, especially with the choice of $M$ determining the number of the other parameters.
But what if we simplify the model definition - let us for example use the same scale/bandwidth for each kernel, that gives us only one parameter $\lambda$. Furthermore, let's say we specify $\mu_1 ... \mu_M$ based on some heuristic, which would mean we treat it as a hyperparameter.
This gives us 
$$f_{\theta,\lambda}(x) = \sum_{m=1}^{M}\theta_m K_\lambda(\mu_m,x), $$
Besides increased complexity of the involved optimization problem, does treating $\lambda$ as a parameter rather than a hyperparameter have other negative or undesired effects? 

(1) Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The
  elements of statistical learning. Vol. 1. No. 10. New York: Springer
  series in statistics, 2001.

 A: I think your understanding of the issue is generally fine and that to some degree the use of the term hyper-parameter reflects informal conventions rather than strict distinctions. In that sense, informally, I think of hyper-parameters as specifying the algorithm (e.g. how many learners, how many basis functions, how much shrinkage, etc.) To quote Bishop's PRML "variables such as $\alpha$, which control the distribution of model parameters, are called hyper-parameters." In the same context, Rasmussen & Williams in GPML use hyperparameters as the free parameters of the covariance function. (i.e. define the form of the distribution of the data rather than the estimates of that distribution's parameters). To that extent, Murphy's MLPP refers to hyper-parameters as "the parameters of the prior", tight them directly to our prior beliefs about a task's dynamics.
The distinction between the treatment of a $\lambda$ (this being the bandwidth of a kernel, or a regularisation/ridge magnitude) as parameter or hyper-parameter is therefore largely immaterial on its own and contextualised within a more general task. This task is generally consider to be supervised learning (i.e. prediction) but it can also be unsupervised learning like clustering ($k$-means being a prototypical example of an algorithm that is almost entirely hyper-parameter driven). Somewhat interestingly Kuhn & Johnson's APM does not even mention hyper-parameters but refers to them as "tuning parameters". This emphasises how these "parameters" are only relevant through another task and that that's why they are commonly associated with cross-validation procedure. For example, in Principal Component Regression we know a priori the total number of PCs available from a particular dataset. The inclusion/exclusion of PCs is related to a separate prediction task.
So, to address the final question directly, no treating $\lambda$ as a parameter rather than a hyper-parameter does not have negative or undesired effects aside the fact we need to reformulate our optimisation problem to reflect our modelling task rather than simply a "cost function".
A: 
Is the distinction between model parameters and hyper-parameters only about reducing the complexity of the problem or are there implications for the 'model quality' to be considered?

Any time an unobserved variable enters into a statistical model, you have the choice either to estimated this variable from the data when fitting the model, or select its value by other means, and then leave it fixed at that value for the purposes of model-fitting.  This fact gives rise to the distinction between parameters and hyper-parameters, which is related to the use of the variable rather than a distinction that exists strictly in the dependencies in the actual statistical model.  
A "parameter" is estimated in the model-fitting process, whereas a "hyper-parameter" is fixed for the model-fitting process, but it may be varied for the purposes of tuning, model selection, robustness testing, or other statistical purposes outside of the model-fitting step.  In the latter case, the hyper-parameter is chosen by some other method than estimation from the data, and this can include setting its value to a fixed constant, varying it over a given range, or any other procedure that does not use the data.  Since both are unobserved variables in the model, you can switch to treating a parameter as a hyper-parameter (i.e., determine its value by other means instead of estimating it from the data), or you can switch from treating a hyper-parameter to a parameter (i.e., estimate its value from the data rather than determining it by outside means).  These choices will depend on the desired generality of your model in the fitting step, and the other outside analysis you wish to do (e.g., robustness testing).
When statisticians undertake statistical modelling, they generally want to pose a model for the fitting step that is sufficiently general to give a reasonable representation of the data in its fitted form.  Modelling often involves using some "structure" via assumed distributional forms, and so on, and so it is also common to want to test the robustness of the model by seeing what happens when you vary an unobserved variable in the model over a fixed range of values.  This means that statisticians sometimes want to designate variables as model parameters (which are estimated in the model-fitting step) and sometimes want to designate variables as hyper-parameters (used for some other purpose).

An example of hyper-parameters in Bayesian statistics: In the context of Bayesian statistics this same distinction comes up, and this is a useful way to illustrate the distinction.  For example, one might use a Bayesian model for normal data with unit variance and unknown mean:
$$\begin{equation} \begin{aligned}
x_1,...,x_n| \mu, \lambda &\sim \text{IID N}(\text{Mean} = \mu, \text{Variance} = 1) \\[6pt]
\mu | \lambda &\sim \text{N}(\text{Mean} = \mu_0, \text{Variance} = 1/\lambda) \\[6pt]
\lambda &\sim \text{Gamma}(\text{Shape} = \tfrac{\varphi}{2}, \text{Scale} = \tfrac{\varphi}{2}) \\[6pt]
\end{aligned} \end{equation}$$
In this model, the analyst wishes to estimate the unknown population mean $\mu$.  Suppose the analyst wants both the unobserved variables $\mu$ and $\lambda$ to be model parameters (estimated from the data), and wants $\mu_0$ and $\varphi$ to be hyper-parameters, used for robustness testing.  These latter variables are fixed in the estimation step, but varied over a range for the purposes of robustness-testing.  Now, using the mixture representation of the T-distribution, it can be show that this model is equivalent to:
$$\begin{equation} \begin{aligned}
x_1,...,x_n| \mu &\sim \text{IID N}(\text{Mean} = \mu, \text{Variance} = 1) \\[6pt]
\mu &\sim \text{Noncentral-T}(\text{Mean} = \mu_0, \text{df} = \varphi) \\[6pt]
\end{aligned} \end{equation}$$
With this representation we remove reference to the parameter $\lambda$, so that the only variables are the parameter of interest $\mu$ and the hyper-parameters.  In this form we can see that varying $\varphi$ is essentially equivalent to varying the "fatness" of the tails of the prior distribution for the parameter of interest.  The robustness-testing thus consists of varying the location of the prior and the fatness of its tails.
Now, suppose that the analyst is regards this robustness-testing as insufficient, and instead wishes to undertake robustness-testing which alters the variance of the prior distribution over some reasonable range.  In that case, the analyst would alter the model by now treating $\lambda$ as a hyper-parameter, so that $\varphi$ no longer appears at all in the model.  We now have the alternative model form:
$$\begin{equation} \begin{aligned}
x_1,...,x_n| \mu &\sim \text{IID N}(\text{Mean} = \mu, \text{Variance} = 1) \\[6pt]
\mu &\sim \text{N}(\text{Mean} = \mu_0, \text{Variance} = 1/\lambda) \\[6pt]
\end{aligned} \end{equation}$$
You can see that this different choice of treatment of the variables in the model leads to different model form for the purposes of estimation.  In the first model we estimate the parameter $\mu$ using a T-prior with hyper-parameters for its location and the fatness of its tails.  In the second model we estimate the parameter $\mu$ using a normal prior with hyper-parameters for its location and scale.  The choice of these competing models will be determined by the degree to which robustness is desired; in the second case there is broader robustness-testing.
