The remaining country is:
Niger
Things are not in the right order. I think ...
... that this puzzle has to be solved from bottom to top.
Let's begin with the last part: Find the capitals of the given countries and connect the ends.
The capitals are:
Afghanistan [2,3] — Kabul
Vietnam [5,5] — Hanoi
Germany [6,7] — Berlin
Kyrgyzstan [8,8] — Bishkek
Morocco [2,6] — Rabat
Saudi Arabia [2,8] — Riyadh
Macedonia [2,4] — Skopje
Jamaica [8,2] — Kingston
Nepal [5,8] — Kathmandu
Sweden [2,2] — Stockholm
Greenland [4,5] — Godthab
Swaziland [6,6] — Lobamba
Malaysia [1,8] — Kuala Lumpur
Venezuela [6,1] — Caracas
We can put their first letters in a grid according to the given coordinates:
. . . . . C . . .
. S . . . . . K .
. K . . . . . . .
. S . . . . . . .
. . . G H . . . .
. R . . . L . . .
. . . . . B . . .
K R . . K . . B .
. . . . . . . . .
Now connect the ends. My first thought was that we have to make paths in the grid between equal letters. There are two pairs of K's and one pair each of R's, S's and B's, but the C, K, H and G don't pair up. There's one uncertainty: The capital of Swaziland might be Mbabane instead of Lobamba, but that doesn't solve our dilemma. So this is a dead end.
The coordinates correspond to the bold letters in the grid given in the question. If the capital of Swaziland is indeed Mbabane, the bold letter of the grid in the question appears in each capital and we see a pattern emerge:
Kuala Lumpur K → 1
Rabat R → 1
Kabul A → 2
Kingston I → 2
Caracas R → 3
Skopje O → 3
Bishkek H → 4
Riyadh A → 4
Hanoi I → 5
Kathmandu M → 5
Berlin N → 6
Stockholm H → 6
Godthab B → 7
Mbabane E → 7
The positions of the letters make perfect pairs:
┌─────────3 ┌───┐
│ 6─────────┘ 2 │
│ 2───────────┘ │
└─3 ┌─────────┐ │
┌───┘ 7 5───┐ │ │
│ 1─┐ └───7 │ │ │
└─┐ │ ┌───6 │ │ │
1 4 │ │ 5───┘ 4 │
└───┘ └─────────┘
That explains the instruction to replace letters by indices. The layout above seems to be the only way to connect the pairs that uses all grid cells.
The next step is to rotate the grid cells.
"Like Julius" means that we have to Caesar-shift the cells with paths by the numerical value of the corresponding path, so that for example all letters along the path that connects the two 3's are shifted by 3:
N O I C N U S A D
B N I L A G I K U
R C O N A K R Y S
U R O S E A U I H
S A L I N A M A A
S S E O U L M O N
E S N E H T A S B
L E M O R M A L E
S E M A P U T O Y
The positionally first and chronologically last part is to remove a list of countries.
Now we have a regular word search. The grid is 9×9, but four of the names have more than nine letters. Since the whole puzzle is about capitals, we must look for the capitals of these countries, all of which will fit into the grid:
Belgium — Brussels
Greece — Athens
Guinea — Conakry
Italy — Rome
Lesotho — Maseru*
Maldives — Male
Mozambique — Maputo
Norway — Oslo
Paraguay — Asuncion
Philippines — Manila
Rwanda — Kigali
South Korea — Seoul
Tajikistan — Dushanbe
All of these can easily be found in the grid; none of the capitals are hidden diagonally. There seems to be an error, though: We find Roseau, the capital of Dominica, instead of Lesothos's capital Maseru.
Anyway, completing the word search and looking at the remaining letters gives Niamey, the capital of Niger.
Phew, we're done! That was a capital puzzle!