You have a portfolio of credit-risk-free bonds all in the sam currency, so just one yield curve.
You are tasked with setting up a Monte Carlo simulation that would create many different scenarios of changes in your yield curves that "look consistent" with the last several years of history.
I suggest you use principal components. Get the historical time series of daily changes in yield. For simplicity, assume that you have the yields "generic" bonds with the same tenors every day. (Note that you could use these historical time series directly on your bond portfolio to get a "historical VaR" and skip the whole MC exercise.) We will assume that the changes in each yield are lognormally distributed. Run principal components analysis on each curve.
Each PC is a weighted sum of the instruments used to construct the yield curve. The weights (aka loadings) are chosen so the PCs are uncorrelated to each other and that each consecutive PC explains the maximum of the unexplained curve variance. Generally, there will be much fewer PCs than the number of instruments used to build the yield curve. Increasing the number of PCs increasins the portion of yield curve variance explained by the PCs. The first 3 PCs have clear geometric interpretation: the first one is "level" or "parallel shift" (the loadings have the same sign and are close to being equal); the second one is "slope" or "tilt" or "flatness / steepness" or "twist" (the loadings change the sign once); the whird one is "curvature", "bow", or "butterfly" (the loadings change the sign twice); while the higher numbered PCs have less intuitive geometric interpretation ("double humps", the loadings change signs many times). Since you'll be looking at tail risk (VaR is typically 99%) you should not limit yourself to the first 3 PCs, but use at least 6.
Actually, for the sake of generality, let us not assume one currency. You could have bonds in USD, EUR (bunds), GBP (gilts), and other currencies. Each currency has one yield curve with some historical principal components, and you also have FX rates. Assume that the changes in the currency exchange rates are normally distributed. So your $n \times n$ covariance matrix $C$ will have on the diagonal the historical variance of the FX rates and PCs; and off the diagonal, their historical covariance. The matrix will be sparse, with lots of zero correlations between the PCs, but for generality's sake, let us allow non-zero correlations between the FX rates. Assume that $C$ is positive definite so you can use Choleski.
The reason why I suggest using PCs, rather than treating each tenor of the yield curve as a random variable and having each tenor in the covariance matrix is that the MC would generate yield curve perturbations that are very unrealistic (don't look like the history and can't happen in real life).
Now (self-plagiarizing my recent answer here, which has a little more mathematical bckground) you can use Choleski decomposition to find the $n \times n$ matrix $H$ such that $H \times H^T = C$. You generate $Z$ of $n$ normally distributed random numbers. Multiply $Y=HZ$. Each scenario $Y$ is normally distributed with mean 0 and covariance $C$. As I already mentioned, you could skip the MC and just use your historical time series instead of (or even in addition to) $Y$.
The next step is to price your bond portfolio given the market data now. You are given the notional amounts, the coupons, and the maturities. You generate the cash flows of each bond in your portfolio. It would be better if you were given additional indicative information for the bonds, such as the freuency of the coupons (annual? quarterly?) and the daycount convention (30/360? Actual/Actual?). Without it, you can assume that they're like U.S. treasuries. To calculate the market value of the bonds given the yields and the currency exchange rates now, you discount each cash flow using the given yield and add them up; and if the bond is in another currency, then you also multiply by the exchange rate.
To calculate your profit and loss (P&L) under each scenario in $Y$, you note that each scenario in $Y$ contains a change in the FX rates (it is clear how to add that to the rate now); and also the change in the PCs. You multiply the PC change by the loadings to get the impact on the generic instruments in your yield curve. You reprice your bond portfolio under the perturbed FX rates and yield curves and subtract the original value of the portfolio to get the P&L under this scenario.
If you have, for example, 10,000 scenarios in $Y$, and you want 99% VaR, then you pick the 100th worst P&L and call it VaR.
For analysis, it is often interesting to look at the scenarios in $Y$ that led to the worse losses; to consider whether they look realistic, should be hedged, etc.